Перенаправлення
Веб-пошук працює з електронними документами, доступними за певними адресами (посиланнями) в мережі. Проте адреса документа може не бути унікальною, і до одного документа можна дістатися через кілька посилань. Розглянемо особливий випадок цієї ситуації — перенаправлення посилань.
Коли клієнт запитує сторінку за адресою A, сервер може відповісти спеціальним кодом, надаючи нову адресу B, на яку клієнт перенаправляється. Цей процес називається перенаправленням. Сторінка B також може перенаправити клієнта на іншу сторінку C і так далі. Таким чином, один і той самий документ може бути доступним за адресами A, B та C.
Дані про перенаправлення можуть надходити з різних джерел, наприклад, від веб-краулера, який бере посилання A під час сканування і проходить через весь ланцюжок перенаправлень. Іншим джерелом може бути API Twitter: твіти завжди містять скорочені посилання (tinylinks), а посилання на оригінальні документи можна отримати з розширених даних у твітах. Якщо у вас є кілька джерел, можуть виникнути конфлікти: наприклад, спочатку ми отримали дані з Twitter (A->B), а потім краулер бере посилання A, що веде до D. Або ж сервіс міг бути перевантажений, і спочатку краулер отримав помилку при спробі отримати документ A, хоча пізніше сервіс став доступним, і краулер досяг цільового документа з другої спроби. Також посилання може стати недійсним, якщо документ застарів.
Якщо ми хочемо обчислити якусь статистику для документа, наприклад, кількість посилань на цей документ, нам потрібен спосіб привести всі посилання до якогось "спільного знаменника". Найбільш практичним "знаменником" є кінцеве посилання в ланцюжку перенаправлень. U вважається кінцевим посиланням у ланцюжку перенаправлень, якщо немає перенаправлення U->V, що веде до посилання V. Кінцеве посилання в ланцюжку перенаправлень також називатиметься справжньою адресою документа.
Вам надано інформацію про N перенаправлень, кожне з яких є парою i v_i> (1 ≤ i ≤ N), де u_i — це оригінальне посилання, а v_i — це посилання, на яке веде це перенаправлення. Перенаправлення може мати вигляд i NULL>, що означає, що посилання u_{i } є недійсним. Посилання надані в порядку введення, тобто перенаправлення, що відбувається пізніше в списку, містить більш актуальну інформацію.
Напишіть програму для обробки наявної інформації про перенаправлення та визначення справжньої адреси документа для кожного з M посилань.
При вирішенні задачі можуть виникнути такі конфлікти:
якщо ланцюжок перенаправлень для якогось посилання U зациклений, ми вважаємо, що справжня адреса цього посилання — NULL;
якщо для якогось посилання U існує кілька варіантів перенаправлення, ми вважаємо правильним останнє перенаправлення;
якщо немає інформації про перенаправлення для якогось посилання U, ми вважаємо, що справжня адреса цього посилання — U.
Вхідні дані
Перший рядок вхідного файлу містить ціле число N. Кожен з наступних N рядків містить два посилання u_{i }v_i, розділені одним або кількома пробілами.
Рядок номер N+2 містить ціле число M. Наступні M рядків містять посилання q_i, для яких потрібно знайти справжні адреси.
1 ≤ N, M ≤ 100000
0 < |v_i|, |u_i|, |q_i| ≤ 10. (Довжина кожного v_i, u_i, q_i не перевищує 10 символів.)
Посилання можуть містити великі та малі літери, цифри та наступні 15 символів, наведені в лапках: "?!#;().%:+-_ /".
Вихідні дані
Вихідний файл повинен містити M рядків, кожен з яких є справжньою адресою посилання q_i.