Lines

Time limit1sMemory limit2048 MB

Summary

Given three arrays a, b, c, find every index i where line F_i is strictly above all other 3n lines at some real t, and print those indices.

Level: Hard9 of 10
Topics: Geometry, Sorting, Math
Solved: No attempts yet

Problem

Three integer arrays $a$ , $b$ , and $c$ are given, each with $n+1$ elements.

Define $3n+1$ functions $F_0, F_1, \ldots, F_{3n}$ as follows:

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

A function $F_i$ is called 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$ . Find all functions that can be called NeVeR_LosEs.

Input

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$ ).

Output

On the first line, print the number $m$ of functions that can be called NeVeR_LosEs. On the second line, print these $m$ indices $0 \leq i_1 \leq \ldots \leq i_m \leq 3n$ in ascending order.

Examples2

Example 1
Input
```
3
3 1 8 7
9 1 3 1
5 1 1 6
```
Expected output
```
5
1 3 4 7 8
```
Example 2
Input
```
1
1 2
1 2
1 2
```
Expected output
```
2
1 2
```