Nearest Neighbouring City

There are n cities on a plane, each at integer coordinates (x,y); names and coordinates are all distinct. For each query city q, among the other cities that share its x coordinate or its y coordinate, find the one with the smallest Manhattan distance (|Δx|+|Δy|). If several cities are tied in distance, take the one whose name is lexicographically smallest (for example ab<aba<abb). If no other city shares its x or y coordinate, the answer is NONE.

输入格式

The first line contains n. Each of the next n lines describes one city: name c, x, y, separated by spaces. The next line contains m, followed by m lines, each with the name of a query city (guaranteed to be an existing city). 1≤n,m≤100000, 1≤x,y≤10^9; names have length 1..10 and contain only lowercase letters, digits and -.

输出格式

Output m lines; line i is the answer to query i (a city name or NONE).

样例 1

输入：

3
c1 3 3
c2 2 2
c3 1 3
3
c1
c2
c3

输出：

c3
NONE
c1

样例 2

输入：

3
fastcity 23 1
bigbanana 23 10
xyz 23 20
3
fastcity
bigbanana
xyz

输出：

bigbanana
fastcity
bigbanana

样例 3

输入：

3
london 1 1
warsaw 10 10
hackerland 20 10
3
london
warsaw
hackerland

输出：

NONE
hackerland
warsaw

样例说明

Example 1: three cities c1(3,3), c2(2,2), c3(1,3). c1 and c3 share y at distance 2, so the answer is c3; c2 has no collinear city, so the answer is NONE; the answer for c3 is c1. Example 2: all three cities are on x=23: fastcity(23,1), bigbanana(23,10), xyz(23,20); the answers are bigbanana, fastcity, bigbanana in order. Example 3: london(1,1) has no collinear city; warsaw(10,10) and hackerland(20,10) share y and are each other's answer.