#P18079. Card Checking

Card Checking

Card Checking

三名玩家 A,B,CA,B,C 玩一个公开全部手牌的游戏。A,BA,B 同属农民队,CC 是地主。任何玩家出完自己的全部手牌时游戏立即结束:若该玩家是 AA 或 BB,农民队获胜;否则地主获胜。

牌的点数为 11 到 nn,允许出的牌型只有单张和同点数的对子。只有某点数在手中恰有一张时,才可以将其作为单张打出;对子不能拆开。

游戏按轮进行,每轮规则如下:

  1. 领出者必须打出一种合法牌型,可以自由选择点数。
  2. 其余玩家按固定顺序 A→B→C→A→⋯A\to B\to C\to A\to\cdots 行动。每次可以不出,也可以打出与本轮最近一次成功出牌牌型相同、点数严格更大的牌。
  3. 一名玩家成功出牌后,如果另外两名玩家依次都不出,本轮结束。最后一次成功出牌者成为下一轮领出者。

最初由 AA 领出。CC 只剩一张点数为 pcp_c 的牌。字符串 sa,sbs_a,s_b 描述两个农民的手牌:第 ii 个字符为 0、1 或 2,表示该玩家有多少张点数为 ii 的牌。所有玩家都至少有一张牌。

假设双方都采取最优策略,判断农民队能否获胜。

输入格式

第一行整数 TT。每组数据依次包含四行:

  • 整数 nn;
  • 长度为 nn 的字符串 sas_a;
  • 长度为 nn 的字符串 sbs_b;
  • 整数 pcp_c。

输出格式

每组输出一行。农民队可以保证获胜时输出 Yes,否则输出 No。

数据范围

  • 1≤T≤1051\le T\le10^5;
  • 1≤n≤2500001\le n\le250000,1≤pc≤n1\le p_c\le n;
  • 每个字符串只含 0、1、2,且不全为 0;
  • 所有数据的 nn 之和不超过 10610^6。

样例 1

输入:

4
9
001110201
002110211
7
9
110200000
222000000
7
9
222000000
110000000
7
9
111000002
111000210
7

输出:

Yes
No
Yes
No