URI Online Judge | 2118

What Headquarter?

By Thalyson Nepomuceno, Universidade Estadual do Ceará BR Brazil

Timelimit: 1

In Fortaleza, all students wishing to study in the Farias Brito, but as there are many venues in the city, some students are in doubt about which headquarter to enroll.

A student chooses to study at the nearest headquarter where he lives. If there are headquarters with same distance from where he lives, the student chooses to study at the headquarters that won more medals in Olympics. If still remains a tie, the student chooses the oldest headquarter.

The map Fortress can be drawn as a graph, where the vertices represent the sites, and the edges represent the streets (Connecting two sites). The distance between two sites X and Y is given by the minimum number of streets that must be used to arrive at Y from X.

The big boss Parcelo Mena ordered Nhalyson Tepomuceno to make a program that indicates what the best headquarter for the students.

Input

The input consists of multiple lines. The first line contains four integers L, S, Q (1 ≤ L, S, Q ≤ 10^5) and A (1 ≤ A ≤ 10^6), representing the number of sites, the number of headquarters, the numbers of students and the number of streets. Each of the next S lines contains three integers Pi, Mi and Ti (1 ≤ Mi, Ti ≤ 10^9), representing the place where headquarter is located, the number of medals and the number of days that the headquarter was built. Each of the next lines contains two integers X and Y, representing that there is a street that connects the sites X and Y. Each of the next Q lines contains the location of each student who wishes to enroll in Farias Brito.

It is guaranteed that for any two distinct headquarter, they were not built on the same day.

Output

For each location a student who wishes to enroll in Farias Brito, print the headquarter identifier that the student must enroll. If there is no headquarter that is accessible by the student using the streets, print "Noic".

Input Sample Output Sample

3 2 1 2

1 100000 500000

2 100001 499999

1 3

2 3

3

2