Bài tập

Hầm mộ nơi Juliet nằm là một lưới gồm \(m\) dòng và \(n\) cột. Mỗi ô là phòng trống hoặc phòng có quỷ dữ. Từ một phòng có thể sang phòng chung cạnh (trên, dưới, trái, phải); không được bước vào phòng có quỷ.

Lần này Romeo không chỉ muốn biết có đến được phòng Juliet hay không, mà cần một lộ trình cụ thể đi qua các phòng trống để chàng đến nơi thật nhanh. Hãy in ra lộ trình ngắn nhất từ phòng Romeo đến phòng Juliet. Nếu có nhiều lộ trình ngắn nhất, chọn lộ trình có dãy toạ độ (dòng, cột) nhỏ nhất theo thứ tự từ điển, tức là ở mỗi bước chọn ô kế tiếp có dòng nhỏ hơn, nếu bằng nhau thì có cột nhỏ hơn (so sánh dãy ô từ ô đầu tiên trở đi).

Input

• Dòng đầu tiên: hai số nguyên \(m\), \(n\).
• \(m\) dòng tiếp theo, mỗi dòng là xâu gồm \(n\) ký tự không có khoảng trắng: o là phòng trống, x là phòng có quỷ, R là phòng Romeo, J là phòng Juliet (mỗi loại R, J đúng một ô).

Output

• Nếu không đến được: in NO.
• Ngược lại in:
• dòng 1: YES;
• dòng 2: số ô của lộ trình (tính cả ô của Romeo và ô của Juliet);
• các dòng tiếp theo: toạ độ dòng cột (đánh số từ 1) của các ô trên lộ trình, bắt đầu từ ô của Romeo và kết thúc ở ô của Juliet, mỗi ô một dòng.

Constraints

• \(1 \le m, n \le 500\)
• R và J là hai ô khác nhau và đều không có quỷ.

Sample Input 1

4 5
Rooxo
oxooo
oxxxo
ooooJ

Sample Output 1

YES
8
1 1
1 2
1 3
2 3
2 4
2 5
3 5
4 5

Sample Input 2

3 4
Rxoo
oxxJ
ooxo

Sample Output 2

NO

Explanation

Ở ví dụ 1 có hai lộ trình ngắn nhất: đi vòng phía trên hoặc đi xuống cột 1 rồi sang phải dọc hàng cuối. Lộ trình đầu có ô thứ hai là \((1,2)\) nhỏ hơn \((2,1)\) nên được chọn.

Cho dãy số nguyên \(A_1, \dots, A_N\). Phần tử \(A_i\) được gọi là cực đại địa phương nếu nó lớn hơn thực sự mọi phần tử kề nó trong dãy: \(A_1\) chỉ cần lớn hơn \(A_2\), \(A_N\) chỉ cần lớn hơn \(A_{N-1}\), còn phần tử ở giữa phải thoả \(A_{i-1} < A_i > A_{i+1}\).

Hãy đếm số cực đại địa phương của dãy.

Input

• Dòng đầu chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

In ra số cực đại địa phương.

Constraints

• \(2 \le N < 35\).
• \(|A_i| < 10^{18}\).

Sample Input

7
5 8 8 2 7 1 6

Sample Output

2

Explanation

Hai số \(8\) liên tiếp không số nào lớn hơn thực sự số kia nên không tính. Các cực đại địa phương là \(A_5 = 7\) và \(A_7 = 6\).

Cho dãy số nguyên \(A_1, A_2, \dots, A_N\). Một cặp chỉ số \((i, j)\) được gọi là nghịch thế nếu \(i < j\) và \(A_i > A_j\).

Có \(Q\) truy vấn, mỗi truy vấn cho hai số \(L < R\). Với mỗi truy vấn, hãy đếm số cặp nghịch thế \((i, j)\) chỉ xét trong đoạn con \(A_L, A_{L+1}, \dots, A_R\), tức là các cặp thoả \(L \le i < j \le R\) và \(A_i > A_j\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\).

Output

In ra \(Q\) dòng, dòng thứ \(t\) là đáp án của truy vấn thứ \(t\).

Constraints

• \(2 \le N \le 1000\).
• \(0 \le A_i \le 10^6\).
• \(1 \le L < R \le N\).
• Một nửa số test có \(Q = 1\), \(L = 1\), \(R = N\); nửa còn lại có \(1 \le Q \le 20\).

Sample Input

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

Sample Output

4
3
7

Explanation

Với đoạn \([1, 4]\) là dãy \(4, 1, 3, 2\): các cặp nghịch thế là \((4,1), (4,3), (4,2), (3,2)\) nên có \(4\) cặp.

Alice và Peter đều mê sưu tầm thẻ bài. Alice có \(N\) thẻ với giá trị \(A_1, A_2, \dots, A_N\) (xếp theo thứ tự sưu tầm), Peter cũng có \(N\) thẻ với giá trị \(B_1, B_2, \dots, B_N\).

Alice đặt ra \(Q\) câu hỏi. Mỗi câu hỏi cho hai số \(X\), \(Y\): xét \(X\) thẻ đầu tiên của Alice (\(A_1, \dots, A_X\)) và \(Y\) thẻ đầu tiên của Peter (\(B_1, \dots, B_Y\)). Hai nhóm thẻ này được coi là giống nhau nếu tập các giá trị khác nhau xuất hiện trong nhóm thứ nhất bằng đúng tập các giá trị khác nhau xuất hiện trong nhóm thứ hai (số lần lặp của mỗi giá trị không quan trọng).

Với mỗi câu hỏi, hãy trả lời hai nhóm có giống nhau hay không.

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).
• Dòng thứ ba chứa \(N\) số nguyên \(B_1, \dots, B_N\).
• Dòng thứ tư chứa số nguyên \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X\), \(Y\).

Output

In ra \(Q\) dòng, mỗi dòng là Yes nếu hai nhóm giống nhau, ngược lại là No.

Constraints

• \(1 \le N, Q \le 2 \times 10^5\)
• \(1 \le A_i, B_i \le 10^9\)
• \(1 \le X, Y \le N\)

Sample Input 1

6
4 7 4 9 2 2
9 4 7 2 7 7
4
4 3
3 3
5 4
2 2

Sample Output 1

Yes
No
Yes
No

Explanation

• Câu 1: \(\{4, 7, 9\}\) và \(\{9, 4, 7\}\) giống nhau.
• Câu 2: \(\{4, 7\}\) khác \(\{9, 4, 7\}\).
• Câu 3: \(\{4, 7, 9, 2\}\) và \(\{9, 4, 7, 2\}\) giống nhau.
• Câu 4: \(\{4, 7\}\) khác \(\{9, 4\}\).