В магазин привезли партию новых футболок, состоящую из n штук. Каждая футболка характеризуется тремя параметрами pi, ai и bi, где pi — это цена i-й футболки, ai — цвет i-й футболки спереди, а bi — цвет i-й футболки со спины. Все pi — различны, а величины ai и bi — целые числа от 1 до 3.
Известно, что в магазин придут m покупателей. Каждый из них хочет купить ровно одну футболку. Про каждого из покупателей известен его любимый цвет, cj — любимый цвет j-го покупателя.
Покупатель согласен купить футболку, если хотя бы с одной стороны она его любимого цвета. При этом среди всех футболок, которые покупатель согласен купить, он выберет самую дешёвую. Если в магазине не осталось подходящих футболок, то покупатель не будет ничего покупать. Считайте, что все покупатели приходят по очереди, и обслуживание нового покупателя не начнется, пока не закончится обслуживание предыдущего.
Перед вами стоит задача для каждого покупателя определить цену футболки, которая будет им куплена.
Выходные данные
Выведите в первую строку m целых чисел, причём j-е число должно быть равно стоимости футболки, которую приобретёт покупатель j. Если покупатель j не сможет найти подходящей футболки, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
300 200 400 500 911
1 2 1 2 3
2 1 3 2 1
6
2 3 1 2 1 1
|
200 400 300 500 911 -1
|
|
2
|
2
1000000000 1
1 1
1 2
2
2 1
|
1 1000000000
|