Trang trại nhà MofK gồm ~n~ hàng và ~m~ cột, có một số ô có bò. MofK muốn ngăn trang trại thành 4 phần bằng cách dựng 1 hàng rào ngang và 1 hàng rào dọc cắt nhau (lưu ý hàng rào chạy qua giữa 2 hàng hoặc 2 cột chứ ko chạy xuyên qua hàng/cột). Sau đó MofK đếm số bò ở mỗi phần. Hôm nay tỉnh dậy, MofK thấy hàng rào của mình không cánh mà bay, nhưng bò vẫn đứng yên chỗ cũ. MofK không thể nhớ được mình đã dựng hàng rào ra sao, và cũng không nhớ chính xác số bò ở mỗi phần. Do đó MofK có ~q~ câu hỏi, mỗi câu hỏi có dạng

$$ \begin{array}{|c|c|} \hline a & b \\ \hline c & d \\ \hline \end{array} $$

với ~a,\ b,\ c,\ d~ lần lượt thể hiện số bò ở phần trái trên, phải trên, trái dưới, phải dưới vốn được ngăn cách bởi hai hàng rào. Hãy giúp MofK kiểm tra xem có tồn tại cách ngăn trang trại sao cho số bò khớp với truy vấn của MofK không.

Input

Dòng đầu tiên chứa 3 số nguyên dương ~n,\ m,\ q\ (1 < n,\ m \leq 1000,\ 1 \leq q \leq 5 \cdot 10^5)~ lần lượt thể hiện chiều dài, chiều rộng của trang trại nhà MofK và số lượng câu hỏi.

~n~ dòng tiếp theo, mỗi dòng gồm ~m~ kí tự đại diện trạng thái của mỗi ô đất — ô đất trống được kí hiệu bằng '.', ô đất có bò được kí hiệu bằng 'B' (không có nháy đơn).

~q~ câu hỏi tiếp theo có định dạng tương tự như trên đề bài: Mỗi câu hỏi gồm 2 dòng, mỗi dòng 2 số, tổng gồm 4 số ~a,\ b,\ c,\ d\ (0 \leq a,\ b,\ c,\ d;\ a+b+c+d \leq mn)~ thể hiện số bò ở mỗi ô tương ứng. Dữ liệu đảm bảo tổng số bò trong mỗi câu hỏi của MofK không vượt quá tổng số bò hiện có trên trang trại.

Output

Với mỗi câu hỏi, nếu tồn tại một cách chia thỏa mãn câu hỏi thứ ~i~ của MofK thì in ra YES. Ngược lại, in ra NO.

Scoring

• ~33\%~ số test có ~n, m \le 20, q \le 100~.
• ~33\%~ số test khác ~ 20 < n, m \le 100, q \le 10000~.
• ~34\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 4 3
..B.
.BB.
B..B
1 2
1 1
2 1
0 1
3 1
0 1

Sample Output 1

YES
NO
NO

Notes

Giải thích ví dụ:

Ở truy vấn 1 ta có thể đặt hàng rào như trên.

Ở hai truy vấn còn lại không có cách chia chuồng thỏa mãn

MofK và ngfam tham gia trò chơi oẳn tù tì , người thua sẽ làm hết deadline của người thắng trong ngày 30/4 - 1/5 sắp đến. Trò chơi được diễn ra trong ~n~ ván , nhưng vì MofK có khả năng đọc được suy nghĩ nên đã tìm ra được xâu gồm ~n~ ký tự có dạng R, P và S (tương ứng với đá, giấy và kéo) thể hiện nước đi của ngfam trong ~n~ ván tới. Để không bị ngfam nghi ngờ MofK không thể chọn nước đi cho ~k~ ván liên tiếp giống nhau .Mặt khác việc thắng quá nhiều hoặc thua quá nhiều thì sẽ bị nghi ngờ nên MofK quyết định sẽ thắng đúng ~m~ ván (những ván còn lại thua hay hòa không quan trọng). Hãy tìm ra một cách giúp MofK chơi thỏa mãn , nếu không tồn tại cách chơi nào thỏa mãn thì in ra ~-1~.

Input

Dòng đầu tiên chứa một số nguyên ~T~ ~(1 \le T \le 3)~ là số lượng bộ dữ liệu.

~T~ nhóm dòng sau:

Dòng đầu tiên là 3 số nguyên dương ~n, k. m~ ~(3 \le n \le 5 \times 10^{5}, 2 \le k \le n, 0 \le m \le n)~.

Dòng thứ 2 là xâu ký tự độ dài ~n~ mỗi ký tự có dạng R, P, S thể hiện nước đi của ngfam trong ~n~ ván.

Output

~T~ dòng là xâu ký tự độ dài ~n~ thể hiện 1 cách chơi thỏa mãn các bộ dữ liệu theo thứ tự nhập vào , nếu không tồn tại thì in ra ~-1~. Nếu có nhiều đáp thỏa mãn, in ra đáp án bất kì.

Sample Input

2
6 2 5
RPPPSS
6 2 4
RPPPSS

Sample Output

-1
PSPSRS

Scoring

• ~20\%~ số test thỏa mãn ~3 \le n \le 15~.

• ~20\%~ số test thỏa mãn ~3 \le n \le 5\times 10^{3}~.

• ~60\%~ số test còn lại không có điều kiện gì thêm.

Một hôm nọ, MofK được sư phụ cho mượn một binh khí đặc biệt là dãy nhị phân ~s~ để luyện tập tuyệt kĩ "thần tốc hậu tố". Với võ công cao cường, chỉ trong chốc lát MofK đã vận được dãy hậu tố ~p~ của ~s~. Tuy nhiên vì chưa thật sự thuần thục, phần nội công dư thừa của y đã đốt cháy binh khí của sư phụ. Không hề lo sợ, y ranh ma nghĩ rằng mình có thể rèn lại binh khí ~s~ từ dãy ~p~ vận được. Sau khi rèn lại dãy ~s~, MofK lại thấy không giống với dãy của sư phụ đưa cho mình, lúc này y mới thực sự hoảng hốt vì nhận ra có rất nhiều dãy ~s~ khác nhau có thể dùng để vận ra cùng một hậu tố ~p~. MofK rơi vào hoang mang...

Cho ~p~ là một hoán vị của dãy ~1, 2, 3,..., n~, hãy đếm số lượng dãy nhị phân độ dài ~n~ có dãy hậu tố (suffix array) là ~p~.

Dãy hậu tố ~p~ của một dãy nhị phân ~s~ độ dài ~n~ được định nghĩa như sau: Đặt ~t_i~ là xâu tạo được bằng cách nối các kí tự liên tiếp trong ~s~ từ vị trí ~i~ đến vị trí ~n~. Dãy ~t'~ gồm các phần tử trong ~t~ nhưng được sắp xếp theo thứ tự từ điển tăng dần, khi đó ~p_i~ là vị trí của xâu ~t'_i~ trong ~t~.

Xâu kí tự ~a~ có thứ tự từ điển nhỏ hơn xâu kí tự ~b~ nếu thỏa một trong các điều kiện sau:

+ ~a~ là tiền tố của ~b~.

+ Tồn tại một giá trị nguyên ~i~ thỏa ~a[j] = b[j]~ ~\forall 1 \leq j < i~ và ~a[i] < b[i]~.

Input

Dòng đầu tiên chứa số nguyên ~T~ (~T \leq 20~) là số bộ dữ liệu.

Trong các dòng tiếp theo, mỗi nhóm dòng miêu tả một bộ dữ liệu bao gồm:

+ Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^5~).

+ Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2,..., p_n~ biểu diễn dãy ~p~. Dữ liệu đảm bảo ~p~ là một hoán vị của dãy ~1, 2, 3, ..., n~.

Output

In ra ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả cho bộ dữ liệu tương ứng, chia lấy dư cho ~10^9 + 7~.

Scoring

~50\%~ số test có ~n \leq 15~ với mọi bộ dữ liệu.

~50\%~ còn lại không có ràng buộc gì thêm.

Sample Input 1

2
4
4 1 2 3
4
1 2 3 4

Sample Output 1

1
1

MofK vừa được tặng một món quà là một tấm bảng gồm ~m~ dòng và ~n~ cột, mỗi ô của bảng chứa một chữ cái.

Với tấm bảng vừa nhận được MofK liền nghĩ ra một trò chơi như sau, MofK sẽ xuất phát từ ô ~(1,\ 1)~ và đi đến ô ~(m,\ n)~, ở mỗi bước đi chỉ được đi sang phải hoặc xuống dưới so với ô MofK đang đứng. Khi đi qua mỗi ô MofK ghi lại chữ cái của ô đó để tạo thành một xâu ~s~ gồm ~m + n - 1~ kí tự khi đi đến ô ~(m,\ n)~.

Vì rất yêu thích món quà được tặng nên MofK quyết định sẽ thử mọi cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ và tạo ra tất cả các xâu có thể. Cuối cùng MofK nghĩ ra một công thức tính điểm như sau: với mỗi xâu ~s~, nếu có ~f(s)~ cách đi để tạo thành xâu ~s~ thì MofK sẽ được ~f(s)^2~ điểm.

Vì số lượng cách đi cũng như số lượng xâu tạo ra quá lớn khiến cho MofK không thể tự mình tính toán số điểm theo như công thức mà mình đã đề ra. Bạn hãy giúp MofK tính số điểm của mình nhé.

Input

Dòng đầu nhập hai số nguyên ~m~ và ~n~ ~(m \times n \leq 10^5)~ tương ứng là số hàng và cột của bảng.

~m~ dòng tiếp theo mỗi dòng nhập một xâu gồm ~n~ kí tự miêu tả một hàng trong bảng.

Output

Một số nguyên duy nhất là số điểm mà MofK nhận được (modulo ~10^9 + 7~).

Scoring

Subtask 1 (~30\%~): ~m,n \le 10~

Subtask 2 (~30\%~): ~m\times n \le 5000~

Subtask 3 (~40\%~): Không có điều kiện gì thêm

Sample Input 1

3 4
aaaa
aaab
abaa

Sample Output 1

34

Notes

Trong test ví dụ, Khi thử tất cả cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ sẽ tạo ra các xâu sau:

• ~3~ xâu aaaaaa

• ~4~ xâu aaaaba

• ~3~ xâu aaabaa

Số điểm nhận được là ~3^2 + 4^2 + 3^2 = 34~

MofK có 1 xâu nhị phân ~s~ (xâu chỉ gồm các kí tự ~0~ hoặc ~1~) độ dài ~n~, các kí tự được đánh số từ ~0~ đến ~n-1~. ngk muốn biết xâu ~s~, nhưng thay vì nói thẳng, MofK chỉ đưa cho ngk ~m~ gợi ý có dạng ~c\ l\ r\ k~, trong đó nếu ~c = 0~ thì xâu con ~[l..l+k]~ (gồm các kí tự có chỉ số từ ~l~ đến ~l+k~) bằng xâu con ~[r..r+k]~, còn nếu ~c = 1~ thì xâu con ~[l..l+k]~ ngược hoàn toàn xâu con ~[r..r+k]~, có nghĩa là mọi vị trí tương ứng của 2 xâu đó đều khác nhau.

ngk cho rằng MofK đưa chưa đủ gợi ý để đoán chính xác xâu ~s~, hay có thể đưa ra gợi ý sai, nên ngk muốn tính xem có bao nhiêu xâu nhị phân độ dài ~n~ thỏa mãn cả ~m~ điều kiện đã cho.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~n,m\le 200000~).

~m~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên ~c, l, r, k~ (~0\le c\le 1, 0\le l\le r\lt n,k\le n -1 - r~) mô tả một gợi ý.

Output

In ra số xâu nhị phân độ dài ~n~ thỏa mãn cả ~m~ gợi ý modulo ~10^9+7~ trên một dòng.

Scoring

Subtask ~1~ (~10\%~): ~n,m\le 15~

Subtask ~2~ (~30\%~): ~n,m\le 5000~

Subtask ~3~ (~60\%~): Không có ràng buộc gì thêm.

Sample Input 1

4 2
0 0 2 1
1 0 1 0

Sample Output 1

2

MofK mới mở một startup công nghệ tên là MicrosOFK. Nhờ tài ăn nói của mình, MofK đã tuyển được ~n~ nhân viên. Dù vậy, để thuyết phục họ về làm việc, MofK đã phải chấp nhận yêu cầu về giờ làm việc của họ; cụ thể, nhân viên thứ ~i~ sẽ làm việc từ thời điểm thứ ~l_i~ đến thời điểm thứ ~r_i~ trong ngày (ta giả sử một ngày được chia làm ~10^6~ khoảng thời gian đánh số từ ~1~ đến ~10^6~). Để giúp mọi người hiểu nhau hơn, MofK muốn chia ~n~ nhân viên vào hai bộ phận: frontend và backend (nhân viên của MofK đều có kĩ năng tốt ở cả hai mảng). Sau đó, mỗi ngày MofK sẽ chọn ra hai nhân viên ~i, j~ đến từ hai bộ phận khác nhau và yêu cầu họ làm chung một dự án. Tất nhiên, ~i~ và ~j~ chỉ có thể làm việc cùng nhau khi họ cùng đang ở công ty, do đó thời gian làm việc chung của họ sẽ là phần giao nhau của ~[l_i, r_i]~ và ~[l_j, r_j]~ (nếu hai khoảng này không giao nhau thì thời gian làm việc chung của họ sẽ là ~0~). MofK muốn chọn tất cả các cặp ~(i, j)~ có thể, mỗi cặp đúng một lần, do vậy MofK sẽ mất tổng cộng ~f \cdot b~ ngày để chọn tất cả các cặp, trong đó ~f~ và ~b~ là số nhân viên nằm trong bộ phận frontend và backend.

Để công ty hoạt động hiệu quả nhất, MofK muốn tổng thời gian làm việc chung của tất cả các cặp là lớn nhất có thể. Hãy giúp MofK tìm ra cách chia tối ưu.

Input

Dòng đầu tiên chứa số nguyên dương ~n~, số nhân viên của MofK (~2 \leq n \leq 300 000~).

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i, r_i~ (~1 \leq l_i \leq r_i \leq 10^6~).

Output

Dòng đầu tiên in ra số ~t~, tổng thời gian làm việc chung lớn nhất tìm được.

Dòng thứ hai in ra một xâu ~s~ gồm ~n~ kí tự, trong đó kí tự thứ ~i~ là ~F~ nếu nhân viên thứ ~i~ được phân vào bộ phận frontend, ngược lại kí tự thứ ~i~ là ~B~.

Nếu có nhiều cách chia đạt được kết quả tối ưu, mọi cách chia đó đều được chấp nhận.

Scoring

Có ~20\%~ số test thỏa mãn ~2 \leq n \leq 20~.

Có ~20\%~ số test khác thỏa mãn ~l_i = 1~ với mọi ~1 \leq i \leq n~.

~60\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3
1 2
3 4
5 6

Sample Output 1

0
FFF

Sample Input 2

3
1 2
3 4
1 4

Sample Output 2

4
BBF

Notes

Trong ví dụ thứ nhất, giờ làm việc của cả ~3~ nhân viên đều không giao nhau, do vậy mọi cách chia đều cho kết quả ~0~ và đều được chấp nhận.

Trong ví dụ thứ hai, nhân viên ~1~ và nhân viên ~2~ đều có thời gian làm việc chung với nhân viên ~3~ là ~2~; trong khi đó, thời gian làm việc chung của nhân viên ~1~ và nhân viên ~2~ là ~0~. Vậy cách tối ưu là chia nhân viên ~1, 2~ vào một bộ phận và nhân viên thứ ~3~ vào bộ phận còn lại.