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

There are $N$ cube-shaped boxes of the same size, numbered $1,2,\ldots,N$. Each face of each box is colored either black or white. The colors of the six faces of the $i$-th box are denoted by $u_i,d_i,f_i,b_i,l_i$, and $r_i$, as shown in Figure E-1. Here, each of $u_i,d_i,f_i,b_i,l_i$, and $r_i$ is either `B` or `W`, where `B` represents black and `W` represents white.  *Figure E-1: Correspondence between the input and the faces of a box.* You are given $Q$ queries. For each $q$ ($1\le q\le Q$), the $q$-th query specifies two integers $s_q$ and $t_q$. Using all the boxes numbered $s_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 $q$ ($1\le q\le Q$), determine whether it is possible to make a balanced tower using all the boxes numbered $s_q,s_q+1,\ldots,t_q$.

The input consists of a single test case of the following format. ```text 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 $N$ and $Q$ ($1\le N\le2\times10^5$, $1\le Q\le2\times10^5$), representing the number of boxes and the number of queries, respectively. For each $i$ ($1\le i\le N$), the $i$-th of the following $N$ lines contains the six characters $u_i,d_i,f_i,b_i,l_i$, and $r_i$, in this order and **without spaces**. Each character is either `B` or `W` and represents the color of the corresponding face of the $i$-th box as shown in Figure E-1. For each $q$ ($1\le q\le Q$), the $q$-th of the following $Q$ lines contains two integers $s_q$ and $t_q$ ($1\le s_q\le t_q\le N$), representing the range of boxes used in the $q$-th query.

Print $Q$ lines. For each $q$ ($1\le q\le Q$), print `Yes` on the $q$-th line if it is possible to make a balanced tower using all the boxes numbered $s_q,s_q+1,\ldots,t_q$, and print `No` otherwise.