Ba bạn ~A, B, C~ chơi một trò chơi như sau: Có ~N~ số tự nhiên từ ~1~ đến ~N~. Ba bạn chơi lấy số lần lượt theo thứ tự: lượt ~1 - A~, lượt ~2 - B~, lượt ~3 - C~, sau đó lại vòng lại, lượt ~4 - A~, lượt ~5 - B...~

Các bạn lấy số theo luật chơi như sau:

• ~A~ lấy số bé nhất trong dãy nếu là lượt lẻ, lấy số lớn nhất nếu là lượt chẵn;
• ~B~ luôn lấy số bé nhất sau khi ~A~ lấy;
• ~C~ lấy số ngược với ~A~: lấy số lớn nhất trong dãy nếu là lượt lẻ, lấy số bé nhất nếu là lượt chẵn.

Chờ mọi người chơi sẽ rất lâu mà Ban tổ chức lại muốn biết sớm xem ai là người sẽ lấy số ~X~ nên bạn hãy lập trình đưa ra đáp án nhé.

Yêu cầu: Đưa ra tên người chơi lấy số ~X~ theo cách chơi trên.
Dữ liệu: Nhập vào hai số tự nhiên ~N~ và ~X~ (~1 \le X \le N \le 10^9~). Mỗi số trên một dòng
Kết quả: Đưa ra duy nhất một chữ cái viết hoa là tên của người chơi lấy số ~X~.

Ví dụ:

Chấm điểm:

• Nếu chương trình chạy đúng những trường hợp ~1 \le X \le N \le 100~, thí sinh sẽ được ~60~ điểm;
• Nếu chương trình chạy đúng những trường hợp ~1 \le X \le N \le 10^9~ thí sinh sẽ được ~100~ điểm.

Cho một xâu nhị phân độ dài $n$, hãy giúp chàng trai chọn một đoạn liên tiếp của xâu và đảo ngược các kí tự trong đoạn đó (0 thành 1, 1 thành 0) để sau cùng xâu có nhiều kí tự 1 nhất.

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~.
• Dòng thứ hai gồm một xâu nhị phân độ dài ~n~.

Output

• Gồm một số nguyên duy nhất là số kí tự 1 nhiều nhất có thể sau khi thực hiện một lần đảo ngược một đoạn liên tiếp.

Scoring

• Subtask 1 (~50\%~ số điểm): ~n \leq 1000~.
• Subtask 2 (~50\%~ số điểm): ~n \leq {10}^5~.

Example

Input

5
10101

Output

4

Note

Chọn đoạn liên tiếp từ vị trí ~2~ đến vị trí ~4~ ta được xâu 11011.

Bạn được cho một mảng ~a~ gồm ~n~ số nguyên dương, đánh số từ ~1~ đến ~n~. Hãy gọi một mảng là đầy đủ nếu với mọi cặp giá trị ~x~ và ~y~ trong mảng (biết ~x~ và ~y~ không nhất thiết phải khác nhau), với điều kiện ~x \geq y~, thì số ~\left \lfloor \frac{x}{y} \right \rfloor~ (lấy ~x~ chia cho ~y~ rồi làm tròn xuống) cũng phải nằm trong mảng.

Bạn được đảm bảo rằng tất cả các số trong mảng ~a~ đều không vượt quá ~c~. Nhiệm vụ của bạn là kiểm tra xem mảng này có phải là đầy đủ hay không.

Bạn sẽ phải trả lời nhiều truy vấn.

Input

• Dòng đầu tiên gồm một số nguyên dương ~t~ ~(1 \le t \le 10^4)~ là số truy vấn, mỗi truy vấn sẽ có dạng như sau:
  • Dòng đầu chứa hai số nguyên dương ~n,c~ mô tả dãy ~a~ ban đầu và cận trên của các giá trị ~a_i~ trong dãy ~(1 \le n \le 2 \times 10^5, 1 \le C \le 10^7)~.
  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le c)~.
• Gọi ~N~ là tổng ~n~ của các truy vấn, tương tự ~C~ là tổng ~c~ của các truy vấn, dữ liệu đảm bảo ~N \le 10^6~ và ~C \le 10^7~.

Output

• Với mỗi truy vấn, in ra "Yes" (không có dấu ngoặc) nếu dãy đó là dãy đầy đủ, ngược lại in ra "No".

Subtask

• Subtask ~1~ (~10\%~ số điểm): ~N \le 100, C \le 10^7~
• Subtask ~2~ (~20\%~ số điểm): ~N \le 10^5, C \le 10^4~
• Subtask ~3~ (~20\%~ số điểm): ~N \le 1000~
• Subtask ~4~ (~30\%~ số điểm): ~N \le 10^5~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

3
3 7
1 2 5
1 5
5
4 8
1 3 3 7

Sample output 1

Yes
No
No

Chim là loài động vật đại diện cho sự tự do. Châu có nuôi 1 con chim tên là Ển, hiện đang sống tại tọa độ ~(0, 0)~ trên mặt phẳng Descartes và hướng về phía dương của trục ~Ox~. Châu đang có một chuỗi thao tác gồm một số thao tác xác định và chưa xác định:

• ~F~ là 1 thao tác cố định yêu cầu chim đi chuyển 1 đơn vị về hướng hiện tại.
• ~T~ là 1 thao tác chưa xác định. Bạn có thể chọn T là cho chim quay theo chiều kim đồng hồ 90 độ hoặc cho chim quay theo ngược chiều kim đồng hộ 90 độ.

Có ~Q~ truy vấn tương ứng là ~Q~ tọa độ ~(x,y)~. Châu muốn biết xem có thể chọn các thao tác ~T~ tương ứng để chim đến được tọa độ ~(x,y)~ không.

Input:

• Dòng đầu tiên là ~Q~ – số lượng truy vấn.
• Dòng thứ hai là xâu biểu diện các thao tác.
• ~Q~ dòng tiếp theo mỗi dòng chứa tọa độ ~(x,y)~.

Output:

• Dòng thứ ~i~ trả về YES nếu chim có thể đến được ~(x,y)~ ở truy vấn thứ ~i~, ngược lại NO.

Sample Test

Input:

2
FTFFTFF
3 2
0 1

Output:

Yes
No

Giới hạn:

• Subtask 1 (20% số điểm): Độ dài các xâu không vượt quá ~20~ kí tự, ~Q \le 20~.
• Subtask 2 (40% số điểm): Độ dài các xâu không vượt quá ~100~ kí tự, ~Q \le 100~.
• Subtask 3 (40% số điểm): Độ dài các xâu không vượt quá ~4000~ kí tự, ~Q \le 10^5~.