Biểu thức logic có thể được định nghĩa truy hồi như sau:

• "true" là một biểu thức logic,
• "false" là một biểu thức logic,
• nếu \(A\) là một biểu thức logic thì \((A)\) cũng là một biểu thức logic,
• nếu \(A\) và \(B\) đều là biểu thức logic thì \(A\) OPERATOR \(B\) là một biểu thức logic.

Ta gọi OPERATOR là một phép toán logic bất kì, trong bài toán này ta chỉ xét OPERATOR là "and" hoặc "or". "and" và "or" đều là phép toán hai ngôi (nhận hai tham số đều là biểu thức logic) và được định nghĩa như sau:

• \(x\) and \(y\) bằng "true" nếu cả \(x\) và \(y\) đều bằng "true", ngược lại bằng "false".
• \(x\) or \(y\) bằng "true" nếu \(x\) hoặc \(y\) bằng "true", ngược lại bằng "false".

Anh nông dân John có một biểu thức logic có dạng \(x_1\) OPERATOR \(x_2\) OPERATOR \(\ldots\) OPERATOR \(x_{(N+1)/2}\) (\(1 \leq N < 2 \times 10^5\), \(N\) lẻ), trong đó \(x_i\) nhận giá trị là "true" hoặc "false" và OPERATOR là phép toán "and" hoặc "or".

Lưu ý là hai phép toán "and" và "or" không có cùng thứ tự ưu tiên. Phép "and" có thứ tự ưu tiên lớn hơn "or", nên thứ tự các phép toán được thực hiện phải là "and" trước, "or" sau.

Nông dân John có \(Q\) câu hỏi (\(1 \leq Q \leq 2 \times 10^3\)). Trong mỗi câu hỏi, anh ấy xóa đoạn từ \(l\) đến \(r\) (\(1 \leq r, l \leq N\), cả \(l\) và \(r\) đều là số lẻ) trong biểu thức. Sau đó anh ấy nhờ bạn thay thế phần biểu thức đã xóa thành "true" hoặc "false" để cả biểu thức sau khi được đánh giá sẽ nhận được kết quả mong muốn. Hãy giúp John nếu có thể!

Input:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ 2 chứa biểu thức có độ dài \(N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) và "true" hoặc "false" đại diện cho câu hỏi John đưa ra.

Output:

• In ra một chuỗi có độ dài \(Q\), trong đó vị trí thứ \(i\) là Y nếu câu hỏi thứ \(i\) có thể thực hiện được, ngược lại thì in ra N.

Scoring:

• Subtask \(1\): \(N, Q \leq {10}^2\)
• Subtask \(2\): \(N, Q \leq {10}^3\)
• Subtask \(3\): Không có ràng buộc gì thêm.

Example:

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

NYYYNYY

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

YNYY

Nông dân John có \(N\) con bò (\(1 \leq N \leq 10^5\)) và chúng rất thích đi lại quanh nông trường của anh ấy.

Hàng rào của John bao gồm \(P\) cọc (\(4 \leq P \leq 2 \times 10^5\), \(P\) là số chẵn), với mỗi cọc là một điểm phân biệt trên trục tọa độ hai chiều (\(0 \leq x,y \leq 1000\)) được nối với các cọc kề nó bằng đường thẳng song song với trục tung hoặc trục hoành. Vậy nên toàn bộ nông trường tạo thành một đa giác khép kín bao quanh cánh đồng. Đường biên của hàng rào phải đáp ứng những điều kiện như sau: các đoạn của hàng rào chỉ có thể giao nhau ở các đầu mút (chính là các cây cọc), mỗi cây cọc chỉ có thể là đầu mút của hai đoạn hàng rào và các đoạn phải vuông góc với nhau.

Mỗi con bò có một điểm bắt đầu và điểm kết thúc chuyến đi khác nhau dọc theo hàng rào (có thể ở các cây cọc, có thể không). Chúng đi dạo dọc theo hàng rào mỗi ngày từ điểm bắt đầu đến điểm kết thúc. Có hai tuyến đường những con bò có thể đi nếu hàng rào khép kín. Tuy nhiên do có phần lười biếng, chúng sẽ luôn chọn đi con đường ngắn hơn (nếu hai con đường có độ dài bằng nhau, chúng có thể chọn 1 trong hai tuyến đường).

Hãy giúp nông dân John tìm ra khoảng cách mỗi con bò đi mỗi ngày.

Input:

• Dòng đầu tiên chứa \(N\) và \(P\).
• \(P\) dòng tiếp theo, mỗi dòng chứa hai số nguyên đại diện cho vị trí của các cọc hàng rào theo thứ tự theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\) đại diện cho vị trí bắt đầu \((x_1, y_1)\) và vị trí kết thúc \((x_2, y_2)\) của một con bò.

Output:

• In ra \(N\) số nguyên trên mỗi dòng, mỗi số là khoảng cách mà mỗi con bò đi.

Scoring:

• Subtask \(1\): \(0 \leq x, y \leq 100\) và \(N \leq 100\)
• Subtask \(2\): Không có ràng buộc gì thêm.

5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0

2
3
3
4
4

Anh nông dân John có một hoán vị \(p\) có độ dài \(N\) (\(2 \leq N \leq 10^5\)) bao gồm những số nguyên dương từ \(1\) đến \(N\) tượng trưng cho mã gen siêu bò của anh ấy. Do ghen tị với đàn bò nhà anh John, nông dân Nhoj đã đột nhập vào nông trại của John và phá hỏng hoán vị mẫu khiến cho John không thể lai tạo thêm siêu bò. Tuy nhiên do chút tình người còn sót lại, Nhoj đã để lại một số gợi ý để giúp John khôi phục hoán vị của anh ấy. Nhiệm vụ của bạn là giúp nông dân John khôi phục lại hoán vị có thứ tự từ điển nhỏ nhất với ít nhất một phần tử còn lại theo các bước như sau:

Giả sử những gì còn sót lại của hoán vị là \(p'_1, p'_2, ..., p'_n\).

• Nếu \(p'_1 > p'_n\), ghi lại \(p'_2\) và loại bỏ \(p'_1\) khỏi hoán vị
• Ngược lại thì ghi lại \(p'_{n-1}\) và loại bỏ \(p'_n\) khỏi hoán vị.

Sau khi phá bĩnh, nông dân Nhoj đã viết lại \(N - 1\) số nguyên \(h_1, h_2, ..., h_{N-1}\) để giúp John khôi phục hoán vị nhanh hơn. Hãy giúp John khôi phục lại hoán vị hoặc chi ra nếu Nhoj đã mắc lỗi trong việc để lại gợi ý. Lưu ý rằng một hoán vị sẽ nhỏ hơn theo thứ tự từ điển nếu nó nhỏ hơn hoán vị còn lại tại vị trí khác biệt đầu tiên \(i\) giữa hai hoán vị.

Input:

• Dòng đầu tiên chứa \(T\) là số lượng test case (\(1 \leq T \leq 10\)).
• Mỗi test case gồm 2 dòng, dòng thứ nhất chứa số nguyên \(N\) (\(2 \leq N \leq 10^5\)) và dòng thứ 2 chứa \(N - 1\) số nguyên \(h_1, h_2, ... h_{N-1}\) (\(1 \leq h_i \leq N\)).

Output:

• In ra \(T\) dòng đại diện cho kết quả của mỗi test case, trong đó, mỗi dòng in ra kết quả của hoán vị \(p\) sau khi khôi phục hoặc -1 nếu không thể khôi phục.

Scoring:

• Subtask 1: \(N \leq 8\)
• Subtask 2: \(N \leq 100\)
• Subtask 3: Không có ràng buộc gì thêm.

Example:

5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1

1 2
-1
-1
3 1 2 4
1 2 3 4