Lines

시간 제한1초메모리 제한2048 MB

요약

세 배열 a, b, c가 주어졌을 때, 어떤 실수 t에서든 다른 모든 직선보다 위에 있는 직선 F_i의 인덱스를 모두 구합니다.

난이도: 어려움10점 중 9점
유형: 기하, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

길이가 각각 $n+1$ 인 정수 배열 $a$ , $b$ , $c$ 가 주어진다.

다음과 같이 $3n+1$ 개의 함수 $F_0, F_1, \ldots, F_{3n}$ 을 정의한다.

$F_i(t) = it + \max_{\substack{0 \leq x, y, z \leq n \\ x + y + z = i}} (a_x + b_y + c_z)$

함수 $F_i$ 는 $j \neq i$ 인 모든 $j$ 에 대해 $F_i(t) > F_j(t)$ 를 만족하는 실수 $t$ 가 존재하지 않을 때, 그리고 그때에만 NeVeR_LosEs이다. NeVeR_LosEs라고 불릴 수 있는 함수를 모두 찾으라.

입력

첫째 줄에 정수 $n$ ( $1 \leq n \leq 3 \cdot 10^5$ )이 주어진다. 둘째 줄에 배열 $a_0, a_1, \ldots, a_n$ ( $0 \leq a_i \leq 10^9$ )이 주어진다. 셋째 줄에 배열 $b_0, b_1, \ldots, b_n$ ( $0 \leq b_i \leq 10^9$ )이 주어진다. 넷째 줄에 배열 $c_0, c_1, \ldots, c_n$ ( $0 \leq c_i \leq 10^9$ )이 주어진다.

출력

첫째 줄에 NeVeR_LosEs라고 불릴 수 있는 함수의 개수 $m$ 을 출력한다. 둘째 줄에 그 함수의 번호 $0 \leq i_1 \leq \ldots \leq i_m \leq 3n$ 을 오름차순으로 출력한다.

예제2

예제 1
입력
```
3
3 1 8 7
9 1 3 1
5 1 1 6
```
예상 출력
```
5
1 3 4 7 8
```
예제 2
입력
```
1
1 2
1 2
1 2
```
예상 출력
```
2
1 2
```