Colors in Store

A new shipment of n tablecloths has arrived at a store. Each tablecloth is described by three attributes: price (p_i), front color (a_i), and back color (b_i), where p_i is an integer and represents the cost of the ith tablecloth, and a_i and b_i are integers ranging from 1 to 3, indicating the colors of the front and back of the tablecloth, respectively. It is guaranteed that all p_i values are unique.

The store expects m customers to visit, and each customer intends to purchase exactly one tablecloth. For each customer, we know their favorite color (c_j). A customer will buy a tablecloth if either the front or back side matches their favorite color. In such cases, the customer selects the cheapest available option among the tablecloths that match their preferred color. If there are no tablecloths with an acceptable color for the customer, they won't make a purchase. The customers arrive sequentially, and each customer is served only after the previous one has been attended to.

Your task is to calculate the price each customer will pay for the tablecloth they choose.

Input Specification

The first line contains an integer n (1 ≤ n ≤ 200 000), representing the number of tablecloths. The following line provides a sequence of n integers: p₁, p₂, …, p_n (1 ≤ p_i ≤ 1 000 000 000), indicating the prices of the tablecloths. The next line contains a sequence of n integers: a₁, a₂, …, a_n (1 ≤ a_i ≤ 3), representing the front colors of the tablecloths. The subsequent line contains a sequence of n integers: b₁, b₂, …, b_n (1 ≤ b_i ≤ 3), indicating the back colors of the tablecloths. Then, there's a single integer m (1 ≤ m ≤ 200 000), denoting the number of customers. The next line provides a sequence of m integers: c₁, c₂, …, c_m (1 ≤ c_j ≤ 3), signifying the favorite color of each customer. The customers arrive in the order they are listed in the input, and each customer is served only after the previous one has been assisted.

Output Specification

Print one line to the standard output with m space-separated integers, where the jth integer should represent the price of the tablecloth that the jth customer will purchase. If the jth customer decides not to buy anything, print –1 for that customer.

Sample Input

5
300 200 400 500 911
1 2 1 2 3
2 1 3 2 1
6
2 3 1 2 1 1

download as text file

Output for Sample Input

200 400 300 500 911 -1