RAD!

DarkknightRHZ Replay of Comilla Univers...
Limits 2s, 512 MB

In the year 3333, earthly scientists discovered a massive star has blast in a nearby galaxy. Dangerous radiations from the explosion are going to hit planet earth very soon. In response, Planetary Protection Unit (PPU) has set-up NN Radiation Absorbing Device (RAD) through-out the Earth surface and labeled them from 11 to NN. Since, the radiations are coming from very far and also due to the continuous rotation of earth and various other factors, scientists could not calculate exactly from which direction the radiation will hit the planet and they also assume each radiation wave’s wavefront is a straight line of infinity length. The planet Earth is considered as a 2-D grid where, each RAD occupies positive integer coordinates. The first properly functioning RADs that are hit by a radiation wave absorb it.

Your uncle, the chief of the PPU has noticed that there are some RADs which are not necessary at all, that is – either they are malfunctioning or they will never get hit by any radiation wave from any direction. And he decided to disable them to save power (RADs require a lot of energy). Being the chief, he has access to the Status Key of the RADs and their 2D coordinates.

A Status Key is a binary string of length NN containing 0’s and 1’s only. If the XX-th character of the string is a 0, it denotes that the RAD labeled XX is malfunctioning or 1 otherwise.

Consider the following example – Status Key = 1101

Earth surface is represented as a 2-D plane and the labeled circles are RADs.

The radiation wave is entering in a direction parallel to Y-axis. In this scenario, first properly functioning RADs to be hit by the wave are 1 and 2. So, the RADs that need to be disabled are labeled 3 and 4.

Because you are the most talented programmer your uncle has ever seen, he hired you to make a program for PPU that will find out the RADs that are required to be disabled. Provided, the radiation may come from any direction and will always originate from outside the grid. Also, each RAD has different coordinates.

Input

First line of input contains a single integer NN (3N10000003 \le N \le 1000000) denoting the number of RADs. Second line contains a binary string SS of NN characters denoting the Status Key. Then follows N lines, II-th of the next lines contains two positive integers XX and YY (0X,Y20000 \le X, Y \le 2000) denoting the coordinates of RAD labeled II.

Output

In a single line, print the labels (separated by space) of the RADs that are to be disabled in ascending order. If no such RADs are found, print -1.

Samples

InputOutput
10
1110111100
1 1
2 1
9 1
4 4
5 9
2 2
8 2
5 8
5 5
3 3
4 6 7 8 9 10
InputOutput
3
111
3 1
1 3
2 8
-1

Submit

Login to submit.

Statistics

67% Solution Ratio
ovis96Earliest, Dec '17
Reayz77Fastest, 421798.7s
SuperstormLightest, 18 MB
ovis96Shortest, 1361B
Toph uses cookies. By continuing you agree to our Cookie Policy.