猫娘爱钓鱼

题目描述

苏小梨和 FireGuo 正在玩一款经典的扑克牌游戏——“钓鱼”。游戏使用一副标准的 $54$ 张扑克牌，其中包括 $52$ 张普通牌和两张鬼牌（王牌）。两人可以只使用其中的一部分牌。

每张牌均用两个字符表示：

• 普通牌：第一个字符表示花色，第二个字符表示点数。
  • 花色为 C、D、H、S，分别代表梅花（Club）、方块（Diamond）、红桃（Heart）、黑桃（Spade）。
  • 点数为 A、2、3、4、5、6、7、8、9、T、J、Q、K，其中 T 表示 $10$。
• 鬼牌：分别表示为 J1（小王）和 J2（大王）。

牌的匹配规则：

• 两张普通牌的点数相同，即认为匹配，花色不影响匹配。
• 两张鬼牌（J1 与 J2）互相匹配。
• 鬼牌不与任何普通牌匹配，例如 J1 与梅花 J CJ 不匹配。

游戏开始时，苏小梨和 FireGuo 分别持有若干张手牌，桌面中央的公共牌堆初始为空。两人的初始得分均为 $0$。每名玩家的手牌按顺序排列，最前面的牌最先打出。

给定一个正整数阈值 $x$，游戏按照以下规则进行：

1. 轮到某名玩家行动时，如果该玩家当前手牌数量严格小于 $x$，游戏立即结束。
2. 否则，该玩家从自己手牌的最前面取出一张牌，打出并放到公共牌堆的末尾。
3. 如果新牌与公共牌堆中此前的牌都不匹配，则本回合结束。
4. 否则，找到公共牌堆中与新牌匹配且位置最靠后的那张旧牌。当前玩家收走从该旧牌开始直到牌堆末尾的所有牌（包含匹配的两张牌），并按它们在公共牌堆中的原有顺序，依次放到自己手牌的末尾。
5. 每当一名玩家收走牌时，该玩家的得分增加本次收走的牌数。
6. 回合结束后切换玩家。两人交替行动，苏小梨先手行动。

收走的牌会重新进入手牌末尾，在后续回合中可能再次打出、再次被收走。同一张实体牌在不同的收牌事件中可以被重复计分。

现在给定两人的初始手牌，以及 $Q$ 个互相独立的查询。每个查询都从相同的初始手牌、空公共牌堆和双方零分开始。请依次输出各查询对应的游戏结束时双方的最终得分。

查询采用加密输入。 初始令 $last=0$。第 $i$ 个查询输入一个整数 $y_i$，其真实阈值为 $x_i=y_i\oplus last$。若本次查询的答案为 $(A_i,B_i)$，输出后更新 $last=A_i\oplus B_i$，用于解密下一个查询。其中 $\oplus$ 表示按位异或，即 C++ 中的 ^ 运算。

数据保证，对于输入中每个查询解密后的真实阈值，游戏的实际出牌总次数严格小于 $L$。一次出牌指一名玩家执行一次规则2，收牌操作不另计出牌次数。

输入格式

第一行包含四个整数 $H_1,H_2,Q,L$，分别表示苏小梨的初始手牌数、FireGuo 的初始手牌数、查询数量以及出牌次数上界。

第二行是一个长度为 $2H_1$ 的字符串，表示苏小梨的初始手牌序列，每两个字符代表一张牌。

第三行是一个长度为 $2H_2$ 的字符串，表示 FireGuo 的初始手牌序列，每两个字符代表一张牌。

接下来 $Q$ 行，每行一个非负整数 $y_i$，表示第 $i$ 个查询加密后的阈值。真实阈值须按题目描述解密。

输出格式

输出 $Q$ 行，每行两个整数，分别表示该查询对应的游戏结束时苏小梨和 FireGuo 的最终得分，整数之间用一个空格分隔。

样例 1

样例输入 1

2 2 2 100
CAC2
D2D3
2
1

样例输出 1

0 0
2 0

样例说明 1

第一次 $last=0$，真实阈值为 $2\oplus0=2$。双方各打出一张牌后，苏小梨只剩1张牌，游戏结束，答案为 $(0,0)$，更新 $last=0$。

第二次真实阈值为 $1\oplus0=1$。苏小梨打出梅花2时收走方块2和梅花2，得2分。之后 FireGuo 的手牌耗尽，在轮到他行动时游戏结束，答案为 $(2,0)$。

样例 2

样例输入 2

2 2 2 100
C2D3
H2S3
2
3

样例输出 2

0 2
0 4

样例说明 2

第一次真实阈值为2，FireGuo 收走两张点数为2的牌，随后苏小梨手牌数不足，答案为 $(0,2)$，更新 $last=2$。

第二次输入为3，真实阈值为 $3\oplus2=1$。FireGuo 在此游戏中还会收走两张点数为3的牌，答案为 $(0,4)$。

样例 3

样例输入 3

3 3 3 100
C2D3H4
S2C3D4
3
0
5

样例输出 3

0 2
0 4
0 6

样例说明 3

三个查询的解密过程依次为：

• $3\oplus0=3$，答案为 $(0,2)$，更新 $last=2$。
• $0\oplus2=2$，答案为 $(0,4)$，更新 $last=4$。
• $5\oplus4=1$，答案为 $(0,6)$。

输入的加密值可以为0，也可以超过54；只有解密后的真实阈值必须在1～54之间。

数据范围与约定

对于 $100\%$ 的数据，满足：

• $1\le H_1,H_2$；
• $H_1+H_2\le54$；
• 所有初始手牌来自同一副标准54张扑克牌，实体牌互不相同；
• $1\le Q\le10^6$；
• $1\le L\le10^6$；
• $0\le y_i<2^{20}$；
• 解密后的真实阈值满足 $1\le x_i\le54$；
• 每个实际查询的出牌总次数严格小于 $L$。

时间限制

• c++: 1000ms , 其他语言2000ms