B. T-shirt buying

[{"iden":"statement","content":"一家商店新到一包 #cf_span[n] 件T恤。每件T恤由三个整数 #cf_span[pi]、#cf_span[ai] 和 #cf_span[bi] 描述，其中 #cf_span[pi] 是第 #cf_span[i] 件T恤的价格，#cf_span[ai] 是其正面颜色，#cf_span[bi] 是其背面颜色。所有 #cf_span[pi] 的值互不相同，而 #cf_span[ai] 和 #cf_span[bi] 的取值范围为 #cf_span[1] 到 #cf_span[3]。\n\n将有 #cf_span[m] 位顾客光顾商店。每位顾客希望恰好购买一件T恤。对于第 #cf_span[j] 位顾客，我们知道他最喜欢的颜色是 #cf_span[cj]。\n\n如果一件T恤的正面或背面至少有一面是顾客最喜欢的颜色，该顾客就会考虑购买。在所有符合该顾客颜色要求的T恤中，他会选择价格最低的那一件。如果没有符合要求的T恤，该顾客将不购买任何商品。假设顾客依次到来，每位顾客只有在前一位顾客完成购买后才会被服务。\n\n你需要计算每位顾客购买T恤所支付的价格。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——T恤的数量。\n\n第二行包含一个整数序列 #cf_span[p1, p2, ..., pn]（#cf_span[1 ≤ pi ≤ 1 000 000 000]），其中 #cf_span[pi] 表示第 #cf_span[i] 件T恤的价格。\n\n第三行包含一个整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 3]），其中 #cf_span[ai] 表示第 #cf_span[i] 件T恤的正面颜色。\n\n第四行包含一个整数序列 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 3]），其中 #cf_span[bi] 表示第 #cf_span[i] 件T恤的背面颜色。\n\n第五行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 200 000]）——顾客的数量。\n\n第六行包含一个整数序列 #cf_span[c1, c2, ..., cm]（#cf_span[1 ≤ cj ≤ 3]），其中 #cf_span[cj] 表示第 #cf_span[j] 位顾客最喜欢的颜色。顾客将按照输入顺序依次到来，每位顾客只有在前一位顾客完成购买后才会被服务。\n\n请在第一行输出 #cf_span[m] 个整数——第 #cf_span[j] 个整数应为第 #cf_span[j] 位顾客购买的T恤价格。如果第 #cf_span[j] 位顾客未购买任何商品，请输出 _-1_。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——T恤的数量。第二行包含一个整数序列 #cf_span[p1, p2, ..., pn]（#cf_span[1 ≤ pi ≤ 1 000 000 000]），其中 #cf_span[pi] 表示第 #cf_span[i] 件T恤的价格。第三行包含一个整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 3]），其中 #cf_span[ai] 表示第 #cf_span[i] 件T恤的正面颜色。第四行包含一个整数序列 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 3]），其中 #cf_span[bi] 表示第 #cf_span[i] 件T恤的背面颜色。第五行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 200 000]）——顾客的数量。第六行包含一个整数序列 #cf_span[c1, c2, ..., cm]（#cf_span[1 ≤ cj ≤ 3]），其中 #cf_span[cj] 表示第 #cf_span[j] 位顾客最喜欢的颜色。顾客将按照输入顺序依次到来，每位顾客只有在前一位顾客完成购买后才会被服务。"},{"iden":"output","content":"请在第一行输出 #cf_span[m] 个整数——第 #cf_span[j] 个整数应为第 #cf_span[j] 位顾客购买的T恤价格。如果第 #cf_span[j] 位顾客未购买任何商品，请输出 _-1_。"},{"iden":"examples","content":"输入\n5\n300 200 400 500 911\n1 2 1 2 3\n2 1 3 2 1\n6\n2 3 1 2 1 1\n输出\n200 400 300 500 911 -1\n\n输入\n2\n1000000000 1\n1 1\n1 2\n2\n1 1\n输出\n1 1000000000 "}],"time_limit":3000,"memory_limit":262144}

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of t-shirts. Let $ p_i \in \mathbb{Z}^+ $ be the price of t-shirt $ i $, for $ i \in \{1, \dots, n\} $. Let $ a_i \in \{1,2,3\} $ be the front color of t-shirt $ i $. Let $ b_i \in \{1,2,3\} $ be the back color of t-shirt $ i $. Let $ m \in \mathbb{Z}^+ $ be the number of buyers. Let $ c_j \in \{1,2,3\} $ be the favorite color of buyer $ j $, for $ j \in \{1, \dots, m\} $. Let $ T = \{(p_i, a_i, b_i) \mid i \in \{1, \dots, n\}\} $ be the set of t-shirts. Let $ S \subseteq T $ be the set of available t-shirts (initially $ S = T $). **Constraints** 1. $ 1 \le n \le 200{,}000 $ 2. $ 1 \le p_i \le 10^9 $, all $ p_i $ distinct 3. $ 1 \le a_i, b_i \le 3 $ 4. $ 1 \le m \le 200{,}000 $ 5. $ 1 \le c_j \le 3 $ **Objective** For each buyer $ j = 1 $ to $ m $: - Let $ A_j = \{ (p_i, a_i, b_i) \in S \mid a_i = c_j \text{ or } b_i = c_j \} $ - If $ A_j = \emptyset $, then buyer $ j $ pays $ -1 $ - Else, buyer $ j $ buys the t-shirt $ (p^*, a^*, b^*) \in A_j $ with minimal $ p^* $, pays $ p^* $, and removes it from $ S $: $$ S \leftarrow S \setminus \{(p^*, a^*, b^*)\} $$ Output the sequence of prices paid by buyers $ 1 $ to $ m $.