30094번 - 그래서 나는 사진을 그만두었다 스페셜 저지

문제

종경이는 사진 영상과 과학 영상 과목에서 사진을 찍는 과제를 받았다.

종경이는 정보과학세미나2를 수강하는 학생 $N$명을 왼쪽부터 오른쪽으로 일렬로 줄 세워 사진을 찍으려고 한다. 정보과학세미나2를 수강하는 학생은 모두 정보과학을 사랑하는 학생이기에 반드시 Codeforces 레이팅과 Atcoder 레이팅을 가지고 있다. 각 학생은 1ドル$부터 $N$까지의 번호를 가지고 있으며, 학생 $i$의 Codeforces 레이팅과 Atcoder 레이팅은 각각 두 정수 $c_i$와 $a_i$로 표현된다.

종경이가 사진 과목에서 공부한 내용에 따르면, $N$명의 학생이 왼쪽에서 오른쪽으로 일렬로 서서 사진을 찍을 때 학생 $i$의 인물 점수는 $c_i \times l_i + a_i \times r_i$로 정의된다. 이때 $l_i$는 $i$번 학생의 왼쪽에 있는 사람의 수이고, $r_i$는 $i$번 학생의 오른쪽에 있는 사람의 수이다. 사진 점수는 사진에 등장하는 $N$명의 인물 점수를 모두 합한 값으로 정의된다.

종경이는 사진 점수로 가능한 값 중 최솟값과 최댓값, 또 최솟값과 최댓값을 가지도록 학생들이 줄을 서는 방법이 몇 가지인지 알고 싶어 했다. 하지만 종경이는 가능한 모든 배열을 시도해 보며 $N!$장의 사진을 모두 찍다가 지쳐서 사진을 찍는 것을 그만두었고 과학 영상과 사진 영상 과목을 재수강할 위기에 처했다. 여러분이 종경이를 도와주자.

입력

첫째 줄에 $N$이 주어진다.

둘째 줄부터 $N + 1$번째 줄까지 $\left( i + 1 \right)$번째 줄에 $c_i,ドル $a_i$가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 사진 점수의 최솟값과 사진 점수가 최솟값이 되게 줄을 서는 방법의 수를 공백을 사이에 두고 출력한다.

둘째 줄에 사진 점수가 최솟값이 되도록 학생들이 줄을 서는 방법 $x_1, x_2, \cdots, x_N$을 공백을 사이에 두고 출력한다. 쉼표는 출력하지 않는다. 왼쪽으로부터 $i$번째에 학생 $x_i$가 선다는 것을 의미한다. $(1 \le i \le N)$

셋째 줄에 사진 점수의 최댓값과 사진 점수가 최댓값이 되게 줄을 서는 방법의 수를 공백을 사이에 두고 출력한다.

넷째 줄에 사진 점수가 최댓값이 되도록 학생들이 줄을 서는 방법 $y_1, y_2, \cdots, y_N$을 공백을 사이에 두고 출력한다. 쉼표는 출력하지 않는다. 왼쪽으로부터 $i$번째에 학생 $y_i$가 선다는 것을 의미한다. $(1 \le i \le N)$

줄을 서는 방법의 수는 너무 많을 수 있으니 998ドル,244円,353円$으로 나눈 나머지를 출력한다.

사진 점수가 최솟값 또는 최댓값이 되게 하는 방법이 여러 가지 있다면, 그중 어떤 것을 출력해도 좋다.

제한

• 1ドル \le N \le 100,000円$
• $-10^8 \le c_i, a_i \le 10^8$
• 주어지는 모든 수는 정수이다.

힌트