Time limit: 1.0s / Memory limit: 256M

Points: 100

Một xâu được gọi là xâu đối xứng nếu như xâu đó được viết từ phải sang trái thì xâu đó không thay đổi.

Cho một xâu ~S~. Hãy tìm độ dài của xâu con dài nhất mà xâu đó không phải là xâu đối xứng.

Input

  • Dòng đầu gồm số nguyên dương ~N~ — độ dài xâu ~S~ (~1 \le N \le 5 \cdot 10^{4}~).

  • Dòng thứ hai gồm xâu ~S~ có độ dài ~N~ gồm toàn chữ cái tiếng Anh in thường.

Output

  • Một dòng duy nhất gồm độ dài xâu con thỏa mãn đề bài.

Scoring

Subtask Điểm Giới hạn
~1~ ~20~ ~N \le 20~
~2~ ~80~ ~N \le 5 \cdot 10^{4}~

Sample Input 1

3
aba

Sample Output 1

2

Sample Input 2

3
aab

Sample Output 2

3

Time limit: 1.0s / Memory limit: 256M

Points: 100

Robot của ~A~ đang đứng tại ô (~x_s, y_s~) trong một bảng hai chiều rộng vô hạn và bạn được ~A~ cho một dãy chỉ dẫn ~S~ gồm ~n~ lệnh L, R, U, D, I để di chuyển robot đến đích (~x_e, y_e~). Ý nghĩa của các lệnh này như sau:

  • L: Robot từ ô (~x, y~) di chuyển sang ô (~x - 1, y~);

  • R: Robot từ ô (~x, y~) di chuyển sang ô (~x + 1, y~);

  • U: Robot từ ô (~x, y~) di chuyển sang ô (~x, y - 1~);

  • D: Robot từ ô (~x, y~) di chuyển sang ô (~x, y + 1~);

  • I: Robot đứng yên tại ô (~x, y~).

Tuy nhiên, dãy chỉ dẫn này có một vài sai số, dẫn đến việc robot có thể không tới được đích. Vì vậy, ~A~ cho bạn được quyền thay đổi một đoạn tối đa ~k~ kí tự liên tiếp để đưa robot đi đến ô đích theo đúng kế hoạch. Nói cách khác, bạn được chọn một đoạn (~l, r~) với ~1 \le l \le r \le n, r - l + 1 \le k~ và gán lại một lệnh bất kỳ cho các chỉ dẫn ~S_l, S_{l + 1}, \dots, S_r~.

Yêu cầu: Hãy cho biết bạn có thể đưa robot đến đích sau khi thực hiện thay đổi trên hay không.

Input

  • Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 10^4~) là số bộ test. Tiếp theo là ~t~ bộ test có cấu trúc như sau:

    • Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ (~1 \le k \le n \le 10^5~).

    • Dòng thứ hai gồm bốn số nguyên ~x_s, y_s, x_e, y_e~ (~-10^9 \le x_s, y_s, x_e, y_e \le 10^9~).

    • Dòng thứ ba là dãy ~S~ gồm ~n~ ký tự L, R, U, D, I — tương ứng với việc đi sang trái, sang phải, lên trên, xuống dưới hoặc đứng yên.

  • Đầu vào đảm bảo ~\Sigma n \le 10^5~.

Output

  • Với mỗi bộ test, in ra "YES" nếu có thể đưa robot đến đích sau khi thay đổi chỉ dẫn, ngược lại in ra "NO".

Scoring

Subtask Điểm Giới hạn
1 ~20\%~ ~k = 1~
2 ~20\%~ ~\Sigma n \le 10^3~
3 ~60\%~ Không có ràng buộc gì thêm

Sample Input 1

1
3 1
1 1 2 2
RDL

Sample Output 1

YES

Sample Input 2

1
5 2
0 0 5 0
LLLLL

Sample Output 2

NO

Notes

  • Ở ví dụ đầu tiên, ta thay đổi ~S_3~ thành "I". Với dãy chỉ dẫn "RDI", robot sẽ đi từ (~1, 1~) đến (~2, 2~).

  • Ở ví dụ thứ hai, ta không có cách nào để đưa robot từ (~0, 0~) đến (~5, 0~) mà chỉ thay đổi tối đa ~2~ chỉ dẫn.


Time limit: 1.0s / Memory limit: 256M

Points: 100

Có một hàng đợi ban đầu trống. Bạn cần xử lý ~q~ truy vấn có dạng sau:

  • Thêm 1 phần tử ~x~ vào cuối hàng

  • Tăng giá trị các phần tử hiện tại trong hàng lên ~v~

  • Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại

Input

  • Dòng đầu tiên gồm số nguyên dương ~q~ là số truy vấn (~1 \le q \le 10^5~).

  • ~q~ dòng tiếp theo mỗi dòng là một truy vấn có dạng như sau:

    • ~1~ ~x~: Thêm 1 phần tử ~x~ vào cuối hàng (~1 \le x \le 10^5~).

    • ~2~ ~v~: Tăng giá trị các phần tử hiện tại trong hàng lên ~v~ (~1 \le v \le 10^5~).

    • ~3~ ~x~: Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại (~1 \le x \le 10^5~).

Output

  • Dòng đầu tiên in ra số lượng phần tử còn lại trong hàng sau ~q~ truy vấn.

  • Dòng thứ hai in ra các phần tử ở trong hàng theo thứ tự từ đầu đến cuối.

Scoring

Subtask Điểm Giới hạn
1 ~30~ ~1 \le q \le 1000~
2 ~30~ Không có truy vấn loại ~3~
3 ~40~ Không có ràng buộc gì thêm

Sample Input 1

9
1 1
1 2
1 3
3 3
2 1
1 3
3 3
2 5
1 6

Sample Output 1

2
7 6

Notes

Ở test ví dụ trên:

  • Sau truy vấn thứ nhất, dãy ~a = \{1\}~

  • Sau truy vấn thứ hai, dãy ~a = \{1,2\}~

  • Sau truy vấn thứ ba, dãy ~a = \{1,2,3\}~

  • Sau truy vấn thứ tư, dãy ~a = \{1,2\}~

  • Sau truy vấn thứ năm, dãy ~a = \{2,3\}~

  • Sau truy vấn thứ sáu, dãy ~a = \{2,3,3\}~

  • Sau truy vấn thứ bảy, dãy ~a = \{2\}~

  • Sau truy vấn thứ tám, dãy ~a = \{7\}~

  • Sau truy vấn cuối cùng, dãy ~a = \{7,6\}~


Time limit: 1.0s / Memory limit: 256M

Points: 100

Cho một đàn bò đánh số theo thứ tự từ ~1~ đến ~n~. Hàng ngày, sẽ có ~k~ sự kiện diễn ra theo thứ tự, sự kiện thứ ~i~ sẽ đảo ngược vị trí các con bò trong đoạn ~[l_i, r_i]~.

Biết rằng ~k~ sự kiện đó hàng ngày đều được diễn ra như nhau. Hãy xác định vị trí từng con bò sau ~d~ ngày.

Input

  • Dòng đầu gồm ba số nguyên dương ~n~, ~k~ và ~d~ (~1 \leq n \leq 10^5, 1 \leq k \leq 100, 1 \leq d \leq 2 \cdot 10^9~).

  • ~k~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l_i~, ~r_i~ tương ứng với việc đảo ngược vị trí các con bò trong đoạn ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.

Output

  • Gồm một dòng gồm ~n~ số nguyên dương, số thứ ~i~ ghi ra số thứ tự của con bò tại vị trí ~i~.

Scoring

Subtask Điểm Giới hạn
1 ~10\%~ ~k \cdot d \le 100~
2 ~20\%~ ~d \le 100~
3 ~70\%~ Không có ràng buộc gì thêm.

Sample Input 1

4 4 2
2 3
1 4
3 4
1 2

Sample Output 1

4 3 2 1

Sample Input 2

4 3 10062006
2 3
1 4
3 4

Sample Output 2

1 2 3 4

Notes

Ở test ví dụ thứ nhất:

  • Ngày đầu tiên:

    • Sau sự kiện ~1~, vị trí của các con bò là: ~1~ ~3~ ~2~ ~4~

    • Sau sự kiện ~2~: ~4~ ~2~ ~3~ ~1~

    • Sau sự kiện ~3~: ~4~ ~2~ ~1~ ~3~

    • Sau sự kiện ~4~: ~2~ ~4~ ~1~ ~3~

  • Ngày thứ hai:

    • Sau sự kiện ~1~: ~2~ ~1~ ~4~ ~3~

    • Sau sự kiện ~2~: ~3~ ~4~ ~1~ ~2~

    • Sau sự kiện ~3~: ~3~ ~4~ ~2~ ~1~

    • Sau sự kiện ~4~: ~4~ ~3~ ~2~ ~1~


Time limit: 1.0s / Memory limit: 256M

Points: 100

Cho một xâu ~S~ độ dài ~N~ chỉ gồm các ký từ '('')'.

Bạn được cho ~Q~ truy vấn, truy vấn thứ ~i~ thuộc một trong hai dạng sau:

  • ~1~ ~x~: Nếu ~S_x~ là '(' thì ~S_x~ sẽ trở thành ')'. Nếu ~S_x~ là ')' thì ~S_x~ sẽ trở thành '('.

  • ~2~ ~x~: Tìm độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~.

Ta định nghĩa một dãy ngoặc đúng như sau:

  • Nếu ~A~ rỗng thì ~A~ là một dãy ngoặc đúng

  • Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ cũng là một dãy ngoặc đúng

  • Nếu ~A~, ~B~ là dãy ngoặc đúng thì ~AB~ cũng là một dãy ngoặc đúng

Một vài ví dụ cho dãy ngoặc đúng: "(())()", "((()))", "()()()".

Input

Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 5 \cdot 10^5)~.

Dòng thứ hai chứa xâu ~S~.

~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~t~ và ~x~ ~(t \in {1, 2}, 1 \le x \le N)~.

Output

Với mỗi truy vấn ~t = 2~, in ra độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~ trên một dòng.

Scoring

Subtask Điểm Giới hạn
1 ~20\%~ ~n, q \le 1000~.
2 ~30\%~ ~n, q \le 10^5~
3 ~50\%~ Không có ràng buộc gì thêm.

Sample Input 1

3 4
(()
2 1
2 2
1 2
2 1

Sample Output 1

0
2
2

Sample Input 2

8 6
)((())()
2 3
1 7
2 2
2 1
1 1
2 1

Sample Output 2

6
6
0
8

Notes

Trong test ví dụ đầu tiên:

  • Ở truy vấn thứ ~1~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là ~\varnothing~.

  • Ở truy vấn thứ ~2~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 2~ là "()".

  • Ở truy vấn thứ ~3~, ~S~ đổi thành "())".

  • Ở truy vấn thứ ~4~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là "()".