Lines

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

요약

각 i에 대해 F_i(t) = i*t + M_i이고 M_i는 x+y+z=i인 a_x+b_y+c_z의 최댓값일 때, 다른 모든 함수를 항상 앞서는 t가 존재하지 않는 i를 모두 찾는다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 기하, 분할 정복, 정렬
정답자: 아직 제출이 없습니다

문제

Given are three arrays of $n+1$ integers: $a$ , $b$ , $c$ .

We define $3n+1$ functions $F\_0, F\_1, \ldots, F\_{3n}$ as follows:

$F\_i(t) = it + \max\limits\_{\substack{0 \leq x, y, z \leq n \\\ x + y + z = i}} {(a\_x + b\_y + c\_z)}\text{.}$

A function $F\_i$ is said to be NeVeR\_LosEs if and only if there does not exist a real number $t$ such that $F\_i(t)>F\_j(t)$ for all $j \neq i$ .

Your task is to find out which functions can be called NeVeR\_LosEs.

입력

The first line contains an integer $n$ ( $1 \leq n \leq 3 \cdot 10^5$ ).

The second line contains the array $a\_0, a\_1, \ldots, a\_n$ ( $0 \leq a\_i \leq 10^9$ ).

The third line contains the array $b\_0, b\_1, \ldots, b\_n$ ( $0 \leq b\_i \leq 10^9$ ).

The fourth line contains the array $c\_0, c\_1, \ldots, c\_n$ ( $0 \leq c\_i \leq 10^9$ ).

출력

On the first line, print an integer $m$ , the number of functions that can be called NeVeR\_LosEs.

On the second line, print $m$ integers $0 \leq i\_1 \leq \ldots \leq i\_m \leq 3n$ , the indices of these functions in ascending order.

예제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
```