33OJ
登录 注册

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

[JAG 2026 Summer Camp #3] Box Tower II

Problem Description

There are NN cube-shaped boxes of the same size, numbered 1,2,…,N1,2,\ldots,N. Each face of each box is colored either black or white.

The colors of the six faces of the ii-th box are denoted by ui,di,fi,bi,liu_i,d_i,f_i,b_i,l_i, and rir_i, as shown in Figure E-1. Here, each of ui,di,fi,bi,liu_i,d_i,f_i,b_i,l_i, and rir_i is either B or W, where B represents black and W represents white.

Figure E-1

Figure E-1: Correspondence between the input and the faces of a box.

You are given QQ queries. For each qq (1≤q≤Q1\le q\le Q), the qq-th query specifies two integers sqs_q and tqt_q.

Using all the boxes numbered sq,sq+1,…,tqs_q,s_q+1,\ldots,t_q, you would like to make a single tower of boxes by rotating each box and then stacking the boxes vertically. After the orientation of each box is determined, all boxes are placed so that their top and bottom faces are horizontal and their bases are exactly aligned. Thus, each of the four sides of the tower consists of exactly one face from each box.

A tower is called balanced if, on each of its four sides, the number of black faces is equal to the number of white faces.

For each qq (1≤q≤Q1\le q\le Q), determine whether it is possible to make a balanced tower using all the boxes numbered sq,sq+1,…,tqs_q,s_q+1,\ldots,t_q.

Input Format

The input consists of a single test case of the following format.

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

The first line contains two integers NN and QQ (1≤N≤2×1051\le N\le2\times10^5, 1≤Q≤2×1051\le Q\le2\times10^5), representing the number of boxes and the number of queries, respectively.

For each ii (1≤i≤N1\le i\le N), the ii-th of the following NN lines contains the six characters ui,di,fi,bi,liu_i,d_i,f_i,b_i,l_i, and rir_i, in this order and without spaces. Each character is either B or W and represents the color of the corresponding face of the ii-th box as shown in Figure E-1.

For each qq (1≤q≤Q1\le q\le Q), the qq-th of the following QQ lines contains two integers sqs_q and tqt_q (1≤sq≤tq≤N1\le s_q\le t_q\le N), representing the range of boxes used in the qq-th query.

Output Format

Print QQ lines.

For each qq (1≤q≤Q1\le q\le Q), print Yes on the qq-th line if it is possible to make a balanced tower using all the boxes numbered sq,sq+1,…,tqs_q,s_q+1,\ldots,t_q, and print No otherwise.

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