33OJ
登录 注册

#P17576. [JAG 2026 Summer Camp #3] Box Tower II

[JAG 2026 Summer Camp #3] Box Tower II

题目描述

有 NN 个大小相同的立方体箱子,编号为 1,2,…,N1,2,\ldots,N。每个箱子的每个面都被涂成黑色或白色。

第 ii 个箱子六个面的颜色分别用 ui,di,fi,bi,li,riu_i,d_i,f_i,b_i,l_i,r_i 表示,其对应关系如图 E-1 所示。这些字符均为 B 或 W,其中 B 表示黑色,W 表示白色。

图 E-1

图 E-1:输入与箱子各个面的对应关系。

给定 QQ 次询问。对于每个 qq(1≤q≤Q1\le q\le Q),第 qq 次询问给出两个整数 sq,tqs_q,t_q。

你想使用编号为 sq,sq+1,…,tqs_q,s_q+1,\ldots,t_q 的全部箱子,将每个箱子旋转后竖直堆叠成一座塔。确定每个箱子的朝向后,摆放所有箱子,使其顶面和底面均保持水平,且底面完全对齐。因此,塔的四个侧面中,每个侧面都恰好包含每个箱子的一个面。

如果塔的四个侧面均满足其中黑色面的数量等于白色面的数量,则称这座塔是平衡的。

对于每个 qq(1≤q≤Q1\le q\le Q),判断能否使用编号为 sq,sq+1,…,tqs_q,s_q+1,\ldots,t_q 的全部箱子搭建一座平衡的塔。

输入格式

输入包含一组测试数据,格式如下。

N Q
u_1d_1f_1b_1l_1r_1
u_2d_2f_2b_2l_2r_2
...
u_Nd_Nf_Nb_Nl_Nr_N
s_1 t_1
s_2 t_2
...
s_Q t_Q

第一行包含两个整数 N,QN,Q(1≤N≤2×1051\le N\le2\times10^5,1≤Q≤2×1051\le Q\le2\times10^5),分别表示箱子的数量和询问次数。

对于每个 ii(1≤i≤N1\le i\le N),接下来 NN 行中的第 ii 行依次包含六个字符 ui,di,fi,bi,li,riu_i,d_i,f_i,b_i,l_i,r_i,字符之间没有空格。每个字符均为 B 或 W,表示图 E-1 中第 ii 个箱子对应面的颜色。

对于每个 qq(1≤q≤Q1\le q\le Q),接下来 QQ 行中的第 qq 行包含两个整数 sq,tqs_q,t_q(1≤sq≤tq≤N1\le s_q\le t_q\le N),表示第 qq 次询问使用的箱子编号范围。

输出格式

输出 QQ 行。

对于每个 qq(1≤q≤Q1\le q\le Q),如果可以使用编号为 sq,sq+1,…,tqs_q,s_q+1,\ldots,t_q 的全部箱子搭建一座平衡的塔,则在第 qq 行输出 Yes;否则输出 No。

4 5
BBWWBW
WWWBBB
BWBBWW
BBBBBB
1 2
2 3
3 4
1 4
2 2
Yes
Yes
No
Yes
No