17079번 - 달콤새콤 스페셜 저지

세상에서 가장 달콤한 축제! 달콤새콤 올림픽이 개최되는 날이 되었다.

이번 올림픽에는 매년 그랬듯이 세 개의 나라, '사탕 나라', '초콜릿 나라', '쿠키 나라' 가 참가한다. 각 나라는 N명의 대표 선수를 선발했으며, 모든 선수 i는 달콤함 a_i와 새콤함 b_i를 갖고 있다. 모든 값들은 사전에 미리 측정되어 있다.

올림픽의 종목은 축제의 이름에서 볼 수 있듯이 딱 두 가지이다. 하나는 '달콤' 이며, 하나는 '새콤' 이다. 올림픽은 아래와 같은 방식으로 총 N경기를 진행한다.

• 각 나라는 N명의 선수들을 내보낼 순서를 정한다. 모든 선수가 정확히 한 번씩 경기에 참여해야 한다.
• 이제 N라운드 동안, 매 라운드마다 공평한 동전을 하나 던져 앞면이면 '달콤', 뒷면이면 '새콤' 을 진행한다.
• 각 라운드에는 각 나라에서 해당 순서를 가진 한 명씩의 선수가 참여한다. 즉, 총 세 명이 경기를 하게 된다.
• '달콤' 경기에서는 달콤함이 가장 높은 선수를 내보낸 나라가 항상 승리하며, '새콤' 경기에서는 새콤함이 가장 높은 선수를 내보낸 나라가 항상 승리한다.
• 만약 동점이 발생한다면, 이번 올림픽의 개최지인 사탕 나라가 우선 순위를 가지며, 그 다음은 전년도 우승자인 초콜릿 나라, 마지막으로 쿠키 나라가 우선 순위를 갖는다.
• 경기를 마친 후, 승리한 나라는 승점 1점을 얻는다. Tie Breaking이 있기 때문에, 항상 정확히 하나의 나라가 승점을 가져가게 된다.

올림픽은 각 라운드에 출전한 선수가 누구인지, 그리고 어떤 종목이 개최되었는지에 따라 총 (N!)³×2^N 가지 서로 다른 형태로 개최될 수 있으며, 각 경우에 대해 개최될 확률은 모두 동일하다.

이번 개최지인 사탕 나라에서는 이번 올림픽에서 꼭 우승을 하고 싶어졌다. 이를 위해 연구에 몰두한 결과, 이상한 물약을 개발하게 되었고, 이 약은 안전하며, 먹는 것이 올림픽 규정에 어긋나지 않는다는 것을 알고 있다. 사탕 나라에서는 자국의 대표 선수 중 일부에게 물약을 마시도록 하여 우승 확률을 높이려 한다.

이상한 물약을 마신 선수는 달콤함이 L_a 이상 R_a 이하의 정수로, 새콤함이 L_b 이상 R_b 이하인 정수로 임의로 변한다. 모든 조합이 선택될 확률은 동일하다.

사탕 나라는 자국의 선수들 중 일부를 뽑아 이상한 물약을 먹게 함으로써, 얻는 승점의 기댓값을 최대화하고 싶다.

개최지인 사탕 나라를 위해, 어떤 선수들에게 이상한 물약을 줘야 할 지, 그리고 승점의 기댓값은 최대 얼마가 될 지 계산해보도록 하자.

첫째 줄에 각 나라의 대표 선수의 수이자 경기가 진행될 라운드 수인 N과 물약의 효능에 관한 값 L_a, R_a, L_b, R_b가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ L_a ≤ R_a ≤ 1000, 1 ≤ L_b ≤ R_b ≤ 1000)

둘째 줄에 사탕 나라의 N명의 대표 선수의 달콤함 a_i가 공백으로 구분되어 주어진다. (1 ≤ a_i ≤ 1000)

셋째 줄에 사탕 나라의 N명의 대표 선수의 새콤함 b_i가 공백으로 구분되어 주어진다. (1 ≤ b_i ≤ 1000)

넷째 줄, 다섯째 줄에는 같은 형식으로 초콜릿 나라의 대표 선수들의 달콤함, 새콤함이 주어지며, 여섯째 줄, 일곱째 줄에는 쿠키 나라의 대표단에 대한 정보가 같은 방식으로 주어진다.

모든 달콤함과 새콤함은 1 이상 1000 이하의 정수이다.

입력으로 주어진 순서는 경기에 참여할 순서가 아닌, 각 나라가 (N!)가지 경우 중 하나를 선택하기 전의 상태임에 유의한다.

사탕 나라가 이상한 물약을 마실 선수를 최적으로 선택했을 때, 사탕 나라가 이번 올림픽에서 얻을 승점의 기댓값을 기약분수 P/Q라 하자. 이 값이 유리수임은 증명된다.

이때, Q의 998,244,353에 대한 곱셈 역원 Q^-1에 대해 첫 줄에 P×Q^-1 mod 998,244,353을 출력한다.

그리고 둘째 줄에는 승점의 기댓값이 최대가 되도록 하기 위해 이상한 물약을 마실 선수의 수 K를 출력한다. (0 ≤ K ≤ N)

K가 0보다 크다면, 셋째 줄에 공백으로 구분하여 이상한 물약을 마실 선수의 번호를 출력한다. 같은 번호가 두 번 이상 나오면 안 되며, 모든 번호는 1 이상 N 이하의 정수여야 한다. 각 선수의 번호는 입력으로 주어진 순서대로 1, 2, ..., N이다.

만일 승점의 기댓값을 최대로 만드는 선수의 집합이 여러 가지라면 K가 최소인 집합을 출력해야 하며, 이러한 집합도 여러 가지일 경우엔 아무 것이나 하나만 출력한다.

X의 P에 대한 곱셈 역원 X^-1이란, X×X^-1 ≡ 1 mod P를 만족하는 정수를 말한다.