题解思路与方法

问题重述

收容所中有 $n$ 只宠物，第 $i$ 只宠物有领养编号 $x_i$（越小优先级越高），两种毛色 $a_i$ 和 $b_i$。有 $m$ 位领养人，依次到来，每位有偏好毛色 $c_j$，只会领养至少一种毛色符合偏好的宠物，并在剩余符合条件的宠物中选领养编号最小的那只。若无心仪宠物，则放弃（输出 $-1$）。

关键思路

1. 按颜色分堆（最小堆） 因为每位领养人只关心某一种颜色，我们可以为三种颜色各维护一个最小堆（min-heap），堆中存储 (领养编号, 宠物下标)。

题目内容

某宠物收容所有 $n$ 只宠物，这些宠物每一只都有两种毛色，第 $i$ 只宠物的第一种毛色为 $ai$，第二种毛色为 $bi$ 。另外根据收容时长，收容所赋予了每个宠物唯一的“领养编号” $xi$ ，可理解为领养优先级，编号越小优先级越高。 近期收容所开放了宠物领养活动。共有 $m$ 个领养人依次来到收容所，每个领养人都有一个偏好的毛色，记为 $ci$ 。领养人只会领养第一种毛色或第二种毛色中至少一种是他们偏好毛色的宠物。如果收容所剩余的宠物中有当前领养人偏好的宠物，则他会选择符合要求的宠物中领养编号最小的那一只宠物。如果没有心仪的宠物(或已经没有剩余的宠物)则会放弃领养。只有当前一位领养人领养结束后(或放弃领养)，下一位领养人才会来到收容所进行领养。领养活动结束后，收容所想要了解每个领养人领养宠物的情况，请你帮助他们进行统计。

输入描述

第一行一个正整数 $n$ ，表示最开始收容所的宠物数量。

第二行 $n$ 个正整数，第 $i$ 个数 $xi$ 表示第 $i$ 只宠物的领养编号。

第三行 $n$ 个正整数，第 $i$ 个数 $ai$ 表示第 $i$ 只宠物的第一种毛色。

第四行 $n$ 个正整数，第 $i$ 个数 $bi$ 表示第 $i$ 只宠物的第二种毛色。

第五行一个正整数 $m$ ，表示领养人数量。

第六行 $m$ 个正整数，第 $i$ 个数 $ci$ 表示第i位领养人偏好的毛色。

$1≤xi≤10^9$，$1≤ai,bi,ci≤3$，$1≤n≤30000$，$1≤m≤100000$

输出描述

输出一行共 $m$ 个数，第 $i$ 个数表示第 $i$ 位领养人领养宠物的“领养编号"，如果第 $i$ 位领养人没有领养宠物，则输出 $-1$ 。

样例1

输入

4
25 10 5 40
1 2 3 1
3 1 2 2
5
2 1 3 2 1

输出

5 10 25 40 -1

说明

第一位领养人偏好毛色 $2$ ：有多只符合毛色的，选择领养编号最小为 $5$ 的(第 $3$ 只)。剩余宠物 $1、2、4$ 。

第二位领养人偏好毛色 $1$ ：有多只符合毛色的，选择领养编号最小为 $10$ 的(第 $2$ 只)。剩余宠物 $1、4$ 。

第三位领养人偏好毛色 $3$ ：符合条件的宠物只有第 $1$ 只，领养编号 $25$ 。剩余宠物 $4$ 。

第四位领养人偏好毛色 $2$ ：符合条件的宠物只有第 $4$ 只，领养编号 $40$ 。无剩余宠物。

第五位领养人偏好毛色 $1$ ：无剩余宠物，输出 $-1$ 。