Description

There is a car race underway. There are $n$ cars on the track, named $g_1,g_2,...,g_n$. The track is an infinitely long straight line. Initially, $g_i$ is located $k_i$ units before the starting line. After the race starts, car $g_i$ travels at a constant speed of $v_i$ units per second. During the race, if a car has ever been in the lead (i.e., no other car is ahead of it), that car will win in the end, and collisions are not a concern. Given all cars’ starting positions and speeds, determine which cars will win.

Input Format

The first line contains a positive integer $n$, the number of cars. The next line contains $n$ integers, giving the starting positions $k_i$ of the $n$ cars in order. The following line contains $n$ integers, giving the constant speeds $v_i$ of the $n$ cars in order.

Output Format

Output two lines. The first line contains the number of winning cars. The second line contains the indices of the winning cars in increasing order, separated by spaces, with no trailing space.

4
1 1 0 0
15 16 10 20

3
1 2 4

Hint

Constraints

• For 100% of the testdata, $1 \le n \le 10^4$, $0 \le k_i \le 10^9$, $0 \le v_i \le 10^9$.

Translated by ChatGPT 5