Spinning Water Cannons

Time limit1sMemory limit1024 MB

Summary

Given N cannons on a circle that rotate and fire jets at fixed periods, find every participant position that is guaranteed to survive until the game ends.

Level: Medium7 of 10
Topics: Simulation, Geometry, Math
Solved: No attempts yet

Statement

Welcome to the Seoul National University Water Bomb festival!

This festival has a game for $N$ people to play together. The game "Spinning Water Cannons" is played with $N$ water cannons placed at equal intervals along the edge of a circular event area. The cannons are numbered 1 to $N$ , and cannon 1, cannon 2, ..., cannon $N$ are placed clockwise. All cannons are fixed to the ground and do not move.

Each cannon rotates clockwise at a constant speed, completing one turn every $2N$ seconds, and never stops. At the initial time, each cannon points at the next cannon clockwise. That is, cannon 1 points at cannon 2, cannon 2 points at cannon 3, ..., and cannon $N$ points at cannon 1.

Cannon $i$ fires a water jet in the direction it is pointing every $T_i$ seconds, including at the initial time. The jet travels along a ray and extends forever without stopping.

Participant $i$ ( $1 \le i \le N$ ) plays at the position of cannon $i$ . If a person is standing on the path of a jet when it is fired, that person is hit by the jet immediately. However, a jet fired by the cannon the participant chose is not counted as a hit. The person at cannon $i$ starts with $A_i$ health, and each hit reduces their health by exactly 1. A person whose health reaches 0 is eliminated 0.5 seconds later. After a person is eliminated, their cannon stops firing from that moment on.

The people who remain until the end receive large prizes. Which positions must be chosen to survive? Find every position that is guaranteed to survive no matter how long the game lasts.

Input

The first line contains $N$ , the number of cannons. ( $2 \le N \le 50$ )

The second line contains the initial health $A_i$ of the person at cannon $i$ , separated by spaces. ( $1 \le A_i \le 1000000000$ )

The third line contains the firing period $T_i$ of cannon $i$ , separated by spaces. ( $1 \le T_i \le 1000$ )

All input values are integers.

Output

On the first line, print the number of positions that are guaranteed to survive.

On the second line, print the cannon numbers of those positions in ascending order, separated by spaces.

Examples4

Example 1
Input
```
3
1 1 2
1 1 1
```
Expected output
```
1
3
```
Example 2
Input
```
3
2 100000 1
1 2 3
```
Expected output
```
1
1
```
Example 3
Input
```
3
1 1 1
1 1 1
```
Expected output
```
0
```
Example 4
Input
```
4
1 10 1 10
2 4 2 4
```
Expected output
```
2
2 4
```