小 L 计划进行 n 场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。
小 L 的赛车有三辆,分别用大写字母 A、B、C 表示。地图一共有四种,分别用小写字母 x、a、b、c 表示。
其中,赛车 A 不适合在地图 a 上使用,赛车 B 不适合在地图 b 上使用,赛车 C 不适合在地图 c 上使用,而地图 x 则适合所有赛车参加。
适合所有赛车参加的地图并不多见,最多只会有 d 张。
n 场游戏的地图可以用一个小写字母组成的字符串描述。例如:S=xaabxcbc 表示小L计划进行 8 场游戏,其中第 1 场和第 5 场的地图类型是 x,适合所有赛车,第 2场和第 3 场的地图是 a,不适合赛车 A,第 4 场和第 7 场的地图是 b,不适合赛车 B,第 6 场和第 8 场的地图是 c,不适合赛车 C。
小 L 对游戏有一些特殊的要求,这些要求可以用四元组 ()来描述,表示若在第 场使用型号为 的车子,则第 场游戏要使用型号为 的车子。
你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。
如果无解,输出 -1。