Remote Training on Programming

It is well known that Web search deals with electronic documents available at certain addresses (links) on the net. However, the address of a document is not necessarily unique, and a single document may be accessed through multiple links. Let us consider a special case of this situation – link redirection.

When the client requests a page at address A, the server responds with a special code providing the address of a new page B, and the client navigates to this address. This process is known as redirection. Page B may as well redirect the client to a new page C and so on. Thus, the same document is made available at addresses A, B and C.

Redirection data can come from various sources, e. g. from a web crawler that takes link A during scheduled crawling and goes through the whole chain of redirects. Another source may be Twitter API: tweets always contain so-called shortened links (tinylinks), and links to the original documents can be obtained from the extended data in tweets. If you have multiple sources, conflicts may arise: suppose, first we obtained data from Twitter (A->B), then the crawler takes link A leading in D. Alternatively, the service may have been overloaded, and at first the crawler received an error attempting to retrieve document A, though later the service became operational, and the crawler reached the target document at the second attempt. Also, the link may become invalid if the document is outdated.

If we want to compute some statistics for the document, say, the number of links to this document, we need a way to bring all the references to some “common denominator”. The most practical “denominator” is the final link in the redirect chain. U is said to be the final link in the redirect chain if there is no redirect U->V leading to link V. The final link in the redirect chain will be also called the true address of the document.

You are given information about N redirects, each being a pair <u_i v_i> (1 ≤ i ≤ N,), where u_i is the original link, and v_i is the link this redirect leads to. The redirect may come in the form <u_i NULL> meaning that link u_i  is invalid. The links are given in the order of entry, i. e., the redirect occurring later in the list contains more up-to-date information.

Write a program to process the available information about redirects and to determine the true address of the document for each of the M links.

When solving the problem, the following conflicts may arise:

§  if the chain of redirects for some link U is looped we suppose that the true address of this link is NULL;

§  if several redirection options exist for some link U we consider the latest redirect as the correct one;

§  if there is no information about redirects for some link U we suppose that the true address of this link is U.

 

Limitations

1 <= N, M <= 100 000

0<|v_i|,|u_i|,|q_i|≤10. (The length of each v_i, u_i, q_i will not exceed 10 characters.)

Links may contain uppercase and lowercase letters, numbers, and the following 15 characters listed inside the quotation marks: “&?!#;().%:+-_~/”.

Input

The first line of the input file contains integer N. Each of the following N lines contains two links u_i  v_i separated by one or more space characters.

Line number N+2 contains integer M. The following M lines contain links q_i, for which the true addresses are to be found.

Output

The output file should contain M lines, each being the true address of link q_i.

Example

	Input	Output
2 youtu.be/J NULL t.co/iqrw youtu.be/J 1 t.co/iqrw		NULL
	Input	Output
5 ti.ny/doc1 ti.ny/doc2 ti.ny/doc2 ti.ny/doc1 ti.ny/doc3 ti.ny/doc2 t.co/asdqt bit.ly/sos bit.ly/sos jfgi.ru 4 ti.ny/doc1 ti.ny/doc3 t.co/asdqt ya.ru		NULL NULL jfgi.ru ya.ru