Ban tổ chức muốn phát quà cho các đội. Có ~T~ đội, được đánh số từ ~0~ đến ~T - 1~. Có ~N~ thí sinh đứng thành một hàng, thí sinh ở vị trí ~i~ thuộc đội ~a_i~.

Mỗi đội được nhận tối đa một hộp quà. Ban tổ chức sẽ tạm dừng phát quà đúng một lần, bỏ qua một đoạn liên tiếp các thí sinh từ vị trí ~\ell~ đến vị trí ~r~, rồi tiếp tục phát quà cho các thí sinh còn lại.

Cần chọn đoạn bị bỏ qua sao cho trong các thí sinh không bị bỏ qua, không có hai thí sinh nào thuộc cùng một đội. Đồng thời, số thí sinh bị bỏ qua là ít nhất có thể.

Yêu cầu

Tìm hai chỉ số ~\ell~ và ~r~ sao cho sau khi bỏ qua tất cả thí sinh có vị trí từ ~\ell~ đến ~r~, mỗi đội xuất hiện không quá một lần trong phần còn lại của hàng, và độ dài đoạn bị bỏ qua là nhỏ nhất.

Nếu có nhiều đáp án tối ưu, in ra một đáp án bất kỳ.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên ~T~ và ~N~ — số đội và số thí sinh.

Dòng thứ hai chứa ~N~ số nguyên ~a_0, a_1, \ldots, a_{N-1}~, trong đó ~a_i~ là đội của thí sinh ở vị trí ~i~.

Đảm bảo mỗi số nguyên từ ~0~ đến ~T - 1~ xuất hiện ít nhất một lần.

Kết quả

In ra hai số nguyên ~\ell~ và ~r~, trong đó ~\ell~ là vị trí đầu tiên bị bỏ qua và ~r~ là vị trí cuối cùng bị bỏ qua.

Các vị trí được đánh số từ ~0~ đến ~N - 1~.

Ví dụ

Ví dụ 1

Input

4 5
1 3 0 2 3

Output

1 1

Ví dụ 2

Input

3 6
1 0 2 2 1 0

Output

0 2

Ví dụ 3

Input

4 8
0 2 0 1 2 1 3 3

Output

2 6

Ví dụ 4

Input

3 6
1 1 2 0 1 0

Output

0 3

Ví dụ 5

Input

4 6
0 1 2 0 3 2

Output

2 3

Ví dụ 6

Input

5 13
3 3 3 1 2 0 3 3 2 1 4 1 0

Output

1 9

Giải thích

Ví dụ 1

Có thể bỏ qua thí sinh ở vị trí ~1~. Khi đó các đội còn lại là ~1, 0, 2, 3~, mỗi đội xuất hiện đúng một lần.

Một đáp án tối ưu khác là bỏ qua thí sinh ở vị trí ~4~.

Ví dụ 2

Có thể bỏ qua đoạn từ ~0~ đến ~2~. Khi đó các đội còn lại là ~2, 1, 0~, mỗi đội xuất hiện đúng một lần.

Một đáp án tối ưu khác là bỏ qua đoạn từ ~3~ đến ~5~.

Ví dụ 3

Đáp án tối ưu là bỏ qua đoạn từ ~2~ đến ~6~. Khi đó các thí sinh còn lại ở vị trí ~0, 1, 7~ thuộc các đội ~0, 2, 3~, không có đội nào nhận quá một hộp quà.

Ví dụ 4

Có thể bỏ qua đoạn từ ~0~ đến ~3~. Khi đó các thí sinh còn lại thuộc các đội ~1~ và ~0~.

Một đáp án tối ưu khác là bỏ qua đoạn từ ~1~ đến ~4~.

Ví dụ 5

Chỉ có thể bỏ qua đoạn từ ~2~ đến ~3~ để tất cả ~4~ đội đều nhận quà.

Ví dụ 6

Tối đa có ~4~ trong ~5~ đội nhận quà. Với đáp án mẫu, các thí sinh còn lại ở vị trí ~0, 10, 11, 12~ thuộc các đội ~3, 4, 1, 0~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le T < N \le 500000~.
• ~0 \le a_i \le T - 1~.
• Mỗi đội từ ~0~ đến ~T - 1~ xuất hiện ít nhất một lần.
• Có ít nhất một đội xuất hiện nhiều hơn một lần.

Chấm điểm

• Subtask~1~ ~(8\%)~: ~N = T + 1~, tức là chỉ có một đội xuất hiện hai lần.
• Subtask~2~ ~(11\%)~: ~N = 2 \cdot T~ và mỗi đội xuất hiện đúng một lần trong nửa đầu, đúng một lần trong nửa sau của hàng.
• Subtask~3~ ~(14\%)~: ~1 \le T < N \le 500~.
• Subtask~4~ ~(21\%)~: ~N = 2 \cdot T~ và mỗi đội xuất hiện đúng hai lần.
• Subtask~5~ ~(22\%)~: ~1 \le T < N \le 5000~.
• Subtask~6~ ~(24\%)~: Không có ràng buộc bổ sung.

Go 2 được chơi trên một lưới ô vuông vô hạn.

Hai người chơi lần lượt đặt các que diêm lên các cạnh của lưới. Mỗi que diêm được đặt trên đúng một cạnh giữa hai ô vuông kề nhau.

Nếu việc đặt một que diêm tạo ra một vùng kín, người đặt que diêm nhận được số điểm bằng diện tích của vùng kín đó, sau đó que diêm vừa đặt bị loại bỏ khỏi lưới. Nếu không tạo ra vùng kín, người chơi nhận ~0~ điểm và que diêm đó được giữ lại trên lưới.

Một vị trí đã từng được đặt que diêm thì không được đặt lại, kể cả khi que diêm ở vị trí đó đã bị loại bỏ.

Cho danh sách các que diêm được đặt theo đúng thứ tự trong ván chơi. Với mỗi lượt đặt, hãy tính số điểm nhận được.

Yêu cầu

Với mỗi que diêm được đặt, hãy in ra số điểm mà lượt đặt đó mang lại.

Dữ liệu

Dòng đầu tiên chứa số nguyên ~N~ — số que diêm được đặt.

~N~ dòng tiếp theo, mỗi dòng mô tả một que diêm, gồm hai số nguyên ~x~, ~y~ và một ký tự ~c~.

Mỗi đỉnh của lưới được xác định bởi tọa độ ~(x, y)~.

Nếu ~c = x~, que diêm được đặt trên cạnh nối ~(x, y)~ với ~(x + 1, y)~.

Nếu ~c = y~, que diêm được đặt trên cạnh nối ~(x, y)~ với ~(x, y + 1)~.

Kết quả

In ra ~N~ dòng. Dòng thứ ~i~ chứa một số nguyên ~s_i~ — số điểm nhận được ở lượt đặt que diêm thứ ~i~.

Ví dụ

Ví dụ 1

Input

4
0 0 x
0 0 y
1 0 y
0 1 x

Output

0
0
0
1

Giải thích

Ví dụ 1

Ba que diêm đầu tiên chưa tạo ra vùng kín nên đều có số điểm là ~0~.

Que diêm thứ ~4~ tạo thành một vùng kín gồm đúng ~1~ ô vuông, nên nhận được ~1~ điểm.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le N \le 3 \cdot 10^5~

~0 \le x_i, y_i \le 10^8~ với mọi ~1 \le i \le N~

~0 \le s_i \le 10^8~ với mọi ~1 \le i \le N~

Các vị trí đặt que diêm trong dữ liệu vào là hợp lệ và không bị lặp.

Chấm điểm

• Subtask~1~ ~(25\%)~: ~N \le 30000~, ~x_i, y_i \le 10000~ với mọi ~1 \le i \le N~.
• Subtask~2~ ~(25\%)~: ~x_i, y_i \le 10000~ với mọi ~1 \le i \le N~.
• Subtask~3~ ~(25\%)~: ~N \le 30000~.
• Subtask~4~ ~(25\%)~: Không có ràng buộc bổ sung.

Có ~N~ con tàu trên mặt phẳng lưới. Ban đầu, tàu thứ ~i~ ở ô có tọa độ ~(x_i, y_i)~, trong đó ~x_i~ và ~y_i~ đều là số chẵn. Mỗi tàu thuộc một trong bốn hạm đội: Bắc, Nam, Đông hoặc Tây.

Trận chiến diễn ra theo từng bước. Ở mỗi bước:

• Tất cả các tàu còn tồn tại đồng thời di chuyển đúng ~1~ ô theo hướng của hạm đội mình.
• Nếu sau khi di chuyển có ít nhất ~2~ tàu cùng nằm trên một ô, tất cả các tàu đó bị chìm và biến mất khỏi bản đồ.

Trận chiến kết thúc khi không còn va chạm nào có thể xảy ra nữa. Một tàu sống sót là tàu vẫn còn tồn tại sau khi trận chiến kết thúc.

Quy tắc di chuyển theo hướng như sau:

• Hạm đội Bắc, ký hiệu ~N~: giảm tọa độ ~y~ đi ~1~.
• Hạm đội Nam, ký hiệu ~S~: tăng tọa độ ~y~ lên ~1~.
• Hạm đội Đông, ký hiệu ~E~: tăng tọa độ ~x~ lên ~1~.
• Hạm đội Tây, ký hiệu ~W~: giảm tọa độ ~x~ đi ~1~.

Yêu cầu

Hãy xác định các tàu sống sót sau khi trận chiến kết thúc.

Dữ liệu

Dòng đầu tiên chứa số nguyên ~N~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~, ~y_i~ và một ký tự ~d_i~, cách nhau bởi dấu cách.

Trong đó:

• ~(x_i, y_i)~ là tọa độ ban đầu của tàu thứ ~i~.
• ~d_i~ là một trong các ký tự ~N~, ~S~, ~E~, ~W~, mô tả hướng di chuyển của tàu thứ ~i~.

Không có hai tàu nào có cùng tọa độ ban đầu.

Kết quả

Với mỗi tàu sống sót, in ra một dòng chứa số nguyên ~i~ — chỉ số của tàu đó.

Các chỉ số tàu sống sót có thể được in theo bất kỳ thứ tự nào.

Nếu không có tàu nào sống sót, không in gì cả.

Ví dụ

Ví dụ 1

Input

7
0 6 E
0 8 E
2 4 E
4 2 S
6 0 S
6 2 S
6 4 S

Output

7

Ví dụ 2

Input

5
4 0 S
0 2 E
2 2 E
4 4 N
6 6 W

Output

5
2

Giải thích

Ví dụ 1

Ở bước thứ ~2~, tàu ~3~ và tàu ~4~ va chạm tại ô ~(4, 4)~ nên cùng bị chìm.

Ở bước thứ ~6~, tàu ~1~ và tàu ~5~ va chạm tại ô ~(6, 6)~. Đồng thời, tàu ~2~ và tàu ~6~ va chạm tại ô ~(6, 8)~.

Tàu duy nhất sống sót là tàu ~7~.

Ví dụ 2

Ở bước thứ ~2~, các tàu ~1~, ~3~ và ~4~ cùng va chạm tại ô ~(2, 4)~ nên đều bị chìm.

Các tàu ~2~ và ~5~ sống sót.

Ràng buộc và chấm điểm

Ràng buộc

~2 \le N \le 2 \cdot 10^5~

~0 \le x_i, y_i \le 10^9~ với mọi ~1 \le i \le N~.

~x_i~ và ~y_i~ đều là số chẵn.

Không có hai tàu nào có cùng tọa độ ban đầu.

Chấm điểm

• Subtask~1~: ~N = 2~.
• Subtask~2~: ~N \le 100~, ~x_i, y_i \le 100~ với mọi ~1 \le i \le N~.
• Subtask~3~: ~N \le 100~, ~x_i, y_i \le 10^5~ với mọi ~1 \le i \le N~.
• Subtask~4~: ~N \le 200~.
• Subtask~5~: ~N \le 5000~.
• Subtask~6~: ~d_i~ chỉ là ~S~ hoặc ~E~ với mọi ~1 \le i \le N~.
• Subtask~7~: không có ràng buộc bổ sung.

Một chương trình có ~N~ dòng, độ dài các dòng lần lượt là ~l_1, l_2, \ldots, l_N~. Dòng cuối cùng luôn là dòng rỗng, tức là ~l_N = 0~.

Con trỏ có thể đặt ở đầu dòng, cuối dòng hoặc giữa hai ký tự liên tiếp. Vì vậy, dòng ~i~ có ~l_i + 1~ vị trí đặt con trỏ, gọi là các cột, được đánh số từ ~1~ đến ~l_i + 1~.

Robert cần di chuyển con trỏ từ vị trí ban đầu ~(s_l, s_c)~ đến vị trí đích ~(e_l, e_c)~ bằng các phím mũi tên. Mỗi lần nhấn một phím được tính là ~1~ thao tác.

Các phím mũi tên ngang hoạt động như sau:

• Nhấn trái:

  • Nếu con trỏ không ở đầu dòng, nó chuyển sang cột trước đó.
  • Nếu con trỏ ở đầu dòng và không phải dòng đầu tiên, nó chuyển đến cuối dòng trước đó.
  • Nếu con trỏ ở đầu tệp, thao tác này không có tác dụng.

• Nhấn phải:

  • Nếu con trỏ không ở cuối dòng, nó chuyển sang cột tiếp theo.
  • Nếu con trỏ ở cuối dòng và không phải dòng cuối cùng, nó chuyển đến đầu dòng tiếp theo.
  • Nếu con trỏ ở cuối tệp, thao tác này không có tác dụng.

Các phím mũi tên dọc hoạt động như sau:

• Nhấn lên:

  • Nếu tồn tại dòng phía trên, con trỏ chuyển lên dòng trước đó và giữ nguyên số cột.
  • Nếu số cột hiện tại vượt quá cuối dòng mới, con trỏ chuyển đến cuối dòng mới.
  • Nếu không tồn tại dòng phía trên, thao tác này không có tác dụng.

• Nhấn xuống:

  • Nếu tồn tại dòng phía dưới, con trỏ chuyển xuống dòng tiếp theo và giữ nguyên số cột.
  • Nếu số cột hiện tại vượt quá cuối dòng mới, con trỏ chuyển đến cuối dòng mới.
  • Nếu không tồn tại dòng phía dưới, thao tác này không có tác dụng.

Yêu cầu

Tính số lần nhấn phím ít nhất để di chuyển con trỏ từ ~(s_l, s_c)~ đến ~(e_l, e_c)~.

Dữ liệu

Dòng đầu tiên chứa số nguyên ~N~ — số dòng của chương trình.

Dòng thứ hai chứa hai số nguyên ~s_l~ và ~s_c~ — vị trí ban đầu của con trỏ.

Dòng thứ ba chứa hai số nguyên ~e_l~ và ~e_c~ — vị trí đích của con trỏ.

Dòng thứ tư chứa ~N~ số nguyên ~l_1, l_2, \ldots, l_N~ — độ dài từng dòng.

Kết quả

In ra một số nguyên duy nhất — số lần nhấn phím ít nhất để di chuyển con trỏ từ ~(s_l, s_c)~ đến ~(e_l, e_c)~.

Ví dụ

Ví dụ 1

Input

5
3 1
2 8
7 10 9 9 0

Output

3

Ví dụ 2

Input

5
1 20
3 25
25 10 40 35 0

Output

16

Giải thích

Ví dụ 1

Có thể đi từ ~(3, 1)~ đến ~(2, 8)~ bằng ~3~ lần nhấn phím: lên, trái, xuống.

Cũng có thể đạt được bằng ~3~ lần nhấn phím theo thứ tự: trái, lên, xuống.

Không thể đạt tới vị trí đích bằng không quá ~2~ lần nhấn phím.

Ví dụ 2

Cách ngắn nhất là nhấn xuống ~2~ lần, sau đó nhấn phải ~14~ lần, tổng cộng ~16~ lần nhấn phím.

Ràng buộc và chấm điểm

Ràng buộc

~1 \le N \le 10^6~

~0 \le l_i \le 10^9~ với mọi ~1 \le i \le N~

~l_N = 0~

~1 \le s_l, e_l \le N~

~1 \le s_c \le l_{s_l} + 1~

~1 \le e_c \le l_{e_l} + 1~

Chấm điểm

• Subtask~1~ ~(5\%)~: ~N \le 2~.
• Subtask~2~ ~(14\%)~: ~N \le 1000~, ~l_i \le 5000~ với mọi ~1 \le i \le N~.
• Subtask~3~ ~(26\%)~: ~N \le 1000~.
• Subtask~4~ ~(11\%)~: ~l_i = l_j~ với mọi ~1 \le i, j \le N - 1~.
• Subtask~5~ ~(44\%)~: Không có ràng buộc bổ sung.

Một đồ chơi có dạng lưới gồm ~H~ hàng và ~W~ cột. Trên lưới có một vật kim loại gồm hai phần:

• Một thanh ngang kích thước ~1 \times K~.
• Một thanh dọc kích thước ~L \times 1~.

Hai thanh này không thể xoay. Mỗi thanh có thể trượt theo phương ngang hoặc phương dọc độc lập với thanh còn lại, nhưng tại mọi thời điểm hai thanh phải giao nhau tại đúng ~1~ ô.

Trên lưới có một số ô chướng ngại vật. Không phần nào của vật kim loại được đi qua chướng ngại vật hoặc vượt ra ngoài lưới, kể cả một phần.

Biết vị trí ban đầu của hai thanh và một ô đích. Cần xác định có thể di chuyển vật kim loại sao cho ô giao nhau của hai thanh nằm đúng tại ô đích hay không.

Yêu cầu

In ra ~YES~ nếu có thể di chuyển vật kim loại đến ô đích, ngược lại in ra ~NO~.

Dữ liệu

Dòng đầu tiên chứa bốn số nguyên ~W~, ~H~, ~K~, ~L~ — chiều rộng và chiều cao của lưới, độ dài thanh ngang và độ dài thanh dọc.

Dòng thứ hai chứa bốn số nguyên ~x_h~, ~y_h~, ~x_v~, ~y_v~:

• ~(x_h, y_h)~ là tọa độ ô ngoài cùng bên trái của thanh ngang ban đầu.
• ~(x_v, y_v)~ là tọa độ ô trên cùng của thanh dọc ban đầu.

Các hàng được đánh số từ ~0~ đến ~H - 1~ từ trên xuống dưới. Các cột được đánh số từ ~0~ đến ~W - 1~ từ trái sang phải. Tọa độ ~x~ là chỉ số cột, tọa độ ~y~ là chỉ số hàng.

~H~ dòng tiếp theo, mỗi dòng gồm ~W~ ký tự mô tả lưới:

• Ký tự ~.~ biểu diễn ô trống.
• Ký tự ~X~ biểu diễn chướng ngại vật.
• Ký tự ~*~ biểu diễn ô đích.

Dữ liệu bảo đảm vị trí ban đầu của vật kim loại là hợp lệ: hai thanh giao nhau tại đúng ~1~ ô, không đè lên chướng ngại vật và không vượt ra ngoài lưới.

Dữ liệu có đúng một ký tự ~*~. Ô đích có thể nằm trên vị trí ban đầu của vật kim loại.

Kết quả

In ra một dòng duy nhất:

• ~YES~ nếu có thể di chuyển vật kim loại sao cho ô giao nhau của hai thanh nằm tại ô đích.
• ~NO~ nếu không thể.

Ví dụ

Ví dụ 1

Input

4 3 2 2
0 1 0 0
.X.*
....
...X

Output

YES

Ví dụ 2

Input

2 3 2 3
0 1 0 0
.X
.*
.X

Output

NO

Giải thích

Ví dụ 1

Có thể di chuyển thanh dọc xuống một ô, sau đó lần lượt di chuyển thanh dọc và thanh ngang sang phải nhiều nhất có thể. Tiếp theo di chuyển thanh dọc lên và sang phải để ô giao nhau đạt tới ô đích, rồi di chuyển thanh ngang lên để hoàn tất.

Ví dụ 2

Thanh dọc không thể di chuyển mà không va vào chướng ngại vật. Vì vậy ô giao nhau không thể đạt tới ô đích.

Ràng buộc và chấm điểm

Ràng buộc

~2 \le W, H \le 1500~

~2 \le K \le W~

~2 \le L \le H~

~0 \le x_h \le W - K~

~0 \le y_h \le H - 1~

~0 \le x_v \le W - 1~

~0 \le y_v \le H - L~

Chấm điểm

-Subtask~1~ ~(14\%)~: ~W, H \le 50~. -Subtask~2~ ~(21\%)~: ~W, H \le 90~. -Subtask~3~ ~(9\%)~: ~W, H \le 300~ và ~K, L \le 10~. -Subtask~4~ ~(29\%)~: ~W, H \le 360~. -Subtask~5~ ~(27\%)~: Không có ràng buộc bổ sung.

Mạng lưới đường cao tốc gồm ~N~ thành phố và ~N - 1~ con đường. Giữa mỗi cặp thành phố luôn tồn tại đúng một đường đi. Mỗi thành phố có đúng một trạm xăng.

Có ~N^2~ chiếc xe di chuyển trong ngày. Với mỗi cặp có thứ tự ~(a, b)~, có đúng một chiếc xe đi từ thành phố ~a~ đến thành phố ~b~ theo đường đi duy nhất giữa hai thành phố đó.

Mọi xe đều có bình xăng dung tích ~K~ lít và tiêu thụ đúng ~1~ lít xăng cho mỗi kilômét di chuyển. Trước khi xuất phát, bình xăng của mỗi xe đều đầy.

Khi đến một thành phố, nếu lượng xăng còn lại không đủ để đi tới thành phố tiếp theo trên hành trình, xe sẽ dừng tại trạm xăng của thành phố đó và đổ đầy bình. Nếu lượng xăng còn lại đủ để đi tiếp, xe sẽ không đổ xăng. Xe được phép đi vào một thành phố với bình xăng rỗng.

Yêu cầu

Tính số chiếc xe đã dừng đổ xăng tại trạm xăng của mỗi thành phố.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ — số thành phố và dung tích bình xăng của mỗi xe.

~N - 1~ dòng tiếp theo mô tả các con đường. Dòng thứ ~i~ chứa ba số nguyên ~u_i~, ~v_i~, ~l_i~, cho biết có một con đường dài ~l_i~ kilômét nối hai thành phố ~u_i~ và ~v_i~.

Các thành phố được đánh số từ ~0~ đến ~N - 1~.

Dữ liệu bảo đảm giữa mọi cặp thành phố tồn tại đúng một đường đi.

Kết quả

In ra ~N~ dòng. Dòng thứ ~i~ chứa số xe đã dừng đổ xăng tại trạm xăng của thành phố ~i~.

Ví dụ

Ví dụ 1

Input

3 1
0 1 1
1 2 1

Output

0
2
0

Ví dụ 2

Input

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

Output

0
3
3
12
8
0

Giải thích

Ví dụ 1

Có ~3~ thành phố nằm trên một đường thẳng, các con đường đều dài ~1~ và dung tích bình xăng là ~1~ lít.

Chỉ có hai xe đi giữa hai thành phố ngoài cùng cần dừng đổ xăng tại thành phố ở giữa.

Ví dụ 2

Có ~6~ thành phố nằm trên một đường thẳng và dung tích bình xăng là ~2~ lít.

Nhiều xe cần dừng tại các thành phố ~3~ và ~4~, do con đường nối hai thành phố này có độ dài ~2~.

Ràng buộc và chấm điểm

Ràng buộc

~2 \le N \le 70000~

~1 \le K \le 10^9~

~0 \le l_i \le K~ với mọi ~0 \le i \le N - 2~.

Chấm điểm

Gọi ~D~ là số con đường lớn nhất nối với cùng một thành phố.

• Subtask~1~ ~(18\%)~: ~N \le 1000~, ~K \le 1000~.
• Subtask~2~ ~(8\%)~: ~D \le 2~ và ~l_i = 1~ với mọi ~0 \le i \le N - 2~.
• Subtask~3~ ~(10\%)~: ~D \le 2~.
• Subtask~4~ ~(12\%)~: ~K \le 10~, ~D \le 10~.
• Subtask~5~ ~(17\%)~: ~K \le 10~.
• Subtask~6~ ~(35\%)~: Không có ràng buộc bổ sung.

Cho hai xâu ~s~ và ~t~. Một xâu con của ~s~ là một đoạn ký tự liên tiếp trong ~s~. Hai xâu con được xem là khác nhau nếu vị trí bắt đầu hoặc vị trí kết thúc khác nhau.

Một xâu con của ~s~ được gọi là ghép được nếu có thể tạo ra nó từ các ký tự của ~t~, mỗi ký tự của ~t~ được dùng không quá số lần xuất hiện của nó.

Yêu cầu

Đếm số cách chọn một xâu con không rỗng của ~s~ ghép được từ các ký tự của ~t~.

Dữ liệu

• Dòng thứ nhất chứa xâu ~s~.
• Dòng thứ hai chứa xâu ~t~.

Kết quả

In ra một số nguyên là số xâu con thỏa mãn.

Ví dụ

Ví dụ ~1~

Input

aaa
aa

Output

5

Ví dụ ~2~

Input

abacaba
abc

Output

15

Giải thích

Ví dụ ~1~

Có ~3~ xâu con độ dài ~1~ và ~2~ xâu con độ dài ~2~ ghép được từ xâu ~t~.

Ví dụ ~2~

Có tổng cộng ~15~ xâu con thỏa mãn.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le |s| \le 10^6~.
• ~1 \le |t| \le 10^6~.
• ~s~ và ~t~ chỉ gồm các chữ cái tiếng Anh in thường.

Gợi ý

Dùng hai con trỏ trên xâu ~s~. Giữ số lượng ký tự còn lại từ ~t~, mở rộng đầu phải tối đa; với mỗi đầu trái, cộng số xâu con hợp lệ bắt đầu tại đó.

Cho một cây gồm ~n~ đỉnh. Mỗi đỉnh được tô một trong hai màu: trắng hoặc đen, được mã hóa lần lượt bởi ~0~ và ~1~.

Cần phá hủy toàn bộ các đỉnh của cây. Có thể thực hiện hai loại thao tác:

• Đổi màu một đỉnh chưa bị phá hủy.
• Chọn một đỉnh chưa bị phá hủy có màu ~c~, sau đó phá hủy toàn bộ các đỉnh màu ~c~ nằm trong cùng một thành phần liên thông với nó, chỉ xét trên các đỉnh chưa bị phá hủy.

Yêu cầu

Tính số thao tác ít nhất cần thực hiện để phá hủy toàn bộ cây.

Dữ liệu

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa xâu ~s~ độ dài ~n~ gồm các ký tự 0 và 1; ký tự thứ ~i~ là màu ban đầu của đỉnh ~i~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~, biểu diễn một cạnh của cây.

Kết quả

In ra một số nguyên là số thao tác ít nhất cần thực hiện.

Ví dụ

Ví dụ ~1~

Input

4
1000
1 2
1 3
1 4

Output

2

Giải thích

Ví dụ ~1~

Có thể đổi màu đỉnh ~1~ thành trắng, sau đó kích hoạt phản ứng dây chuyền từ đỉnh ~1~ để phá hủy toàn bộ cây.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 200000~.
• ~1 \le a_i, b_i \le n~.
• Các cạnh tạo thành một cây.

Gợi ý

Có thể xem mọi thao tác đổi màu thực hiện trước, rồi mới phá hủy. Quy hoạch động trên cây với ~dp[v][0]~, ~dp[v][1]~ là chi phí nhỏ nhất nếu đỉnh ~v~ có màu cuối tương ứng.

Cho một đồ thị vô hướng không có khuyên và không có cạnh lặp.

Một kim cương là một cặp tam giác có chung đúng một cạnh. Hai kim cương được xem là khác nhau nếu tồn tại một cạnh thuộc kim cương này nhưng không thuộc kim cương kia.

Yêu cầu

Đếm số kim cương trong đồ thị đã cho.

Dữ liệu

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~ là số đỉnh và số cạnh của đồ thị.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~, biểu diễn một cạnh nối hai đỉnh ~a_i~ và ~b_i~.

Kết quả

In ra một số nguyên là số kim cương trong đồ thị.

Ví dụ

Ví dụ ~1~

Input

4 4
1 2
2 3
3 4
4 1

Output

0

Ví dụ ~2~

Input

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

Output

1

Ví dụ ~3~

Input

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

Output

6

Giải thích

Ví dụ ~1~

Đồ thị không có cặp tam giác nào có chung một cạnh.

Ví dụ ~2~

Hai tam giác cùng chứa cạnh ~1-3~, tạo thành một kim cương.

Ví dụ ~3~

Đồ thị đầy đủ trên ~4~ đỉnh có ~6~ cách chọn một cặp tam giác chung cạnh.

Ràng buộc và chấm điểm

Ràng buộc

• ~4 \le n, m \le 300000~.
• ~1 \le a_i, b_i \le n~.
• ~a_i \ne b_i~.
• Đồ thị không có cạnh lặp.

Gợi ý

Mỗi kim cương tương ứng với một cạnh có ít nhất ~2~ đỉnh chung kề với cả hai đầu cạnh. Đếm số láng giềng chung của các cặp đỉnh bằng cách duyệt theo bậc để đạt ~O(m\sqrt m)~.

Cho ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Một tập con các số được gọi là tốt nếu ước chung lớn nhất của tất cả các số trong tập con đó lớn hơn ~1~.

Yêu cầu

Tìm kích thước lớn nhất của một tập con tốt.

Dữ liệu

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Kết quả

In ra một số nguyên là kích thước lớn nhất của một tập con tốt.

Ví dụ

Ví dụ ~1~

Input

4
6 15 10 42

Output

3

Ví dụ ~2~

Input

3
2 2 2

Output

3

Ví dụ ~3~

Input

1
35

Output

1

Giải thích

Ví dụ ~1~

Có thể chọn tập ~{6, 15, 42}~, có ước chung lớn nhất bằng ~3~.

Ví dụ ~2~

Chọn cả ~3~ số, ước chung lớn nhất bằng ~2~.

Ví dụ ~3~

Tập chỉ gồm số ~35~ có ước chung lớn nhất bằng ~35~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 1000~.
• ~2 \le a_i \le 10^{18}~.

Gợi ý

Cần tìm ước ~d>1~ chia nhiều số nhất. Thử các thừa số nguyên tố nhỏ, sau đó xét các ~\gcd(a_i,a_j)~ còn lại làm ứng viên.

Cho một bảng ô vuông kích thước ~n \times m~. Mỗi ô ban đầu có màu trắng hoặc đen. Ký tự . biểu diễn ô trắng, ký tự # biểu diễn ô đen.

Một hoa văn được xem là hợp lệ nếu:

• Có ít nhất một ô đen.
• Nếu nối cạnh giữa các ô đen kề nhau theo cạnh, đồ thị thu được có đúng một thành phần liên thông.
• Đồ thị các ô đen không có chu trình đơn.

Có thể đổi màu một số ô, mỗi ô được đổi màu không quá một lần.

Yêu cầu

In ra một hoa văn hợp lệ cần số lần đổi màu ít nhất có thể.

Dữ liệu

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự . hoặc #, mô tả hoa văn ban đầu.

Kết quả

In ra ~n~ dòng, mỗi dòng gồm ~m~ ký tự . hoặc #, mô tả một hoa văn hợp lệ cần số lần đổi màu ít nhất.

Nếu có nhiều đáp án tối ưu, in ra bất kỳ đáp án nào.

Ví dụ

Ví dụ ~1~

Input

3 3
###
#.#
###

Output

###
#.#
##.

Ví dụ ~2~

Input

4 3
##.
.##
###
##.

Output

##.
.##
#.#
###

Ví dụ ~3~

Input

2 3
...
...

Output

#..

Giải thích

Ví dụ ~1~

Cần đổi màu ít nhất ~1~ ô.

Ví dụ ~2~

Cần đổi màu ít nhất ~2~ ô.

Ví dụ ~3~

Cần đổi màu ít nhất ~1~ ô để có ít nhất một ô đen.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 100~.
• ~1 \le m \le 10~.

Gợi ý

Cần biến tập ô đen thành một cây trên lưới. Dùng DP theo profile gãy, trạng thái lưu phân hoạch các ô đen trên biên hiện tại thành các thành phần liên thông.

Cho dãy ~a_1, a_2, \ldots, a_n~. Cần chọn hai chỉ số ~l~ và ~r~ sao cho ~1 \le l < r \le n~.

Gọi:

• ~S_1 = a_1 + a_2 + \cdots + a_l~.
• ~S_2 = a_r + a_{r+1} + \cdots + a_n~.

Yêu cầu

Tìm giá trị nhỏ nhất của ~|S_1 - S_2|~ và một cặp ~l, r~ đạt được giá trị đó.

Dữ liệu

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Kết quả

In ra ba số nguyên: giá trị nhỏ nhất của ~|S_1 - S_2|~, chỉ số ~l~ và chỉ số ~r~.

Nếu có nhiều cặp ~l, r~ tối ưu, in ra bất kỳ cặp nào.

Ví dụ

Ví dụ ~1~

Input

5
5 1 1 1 1

Output

1 1 2

Ví dụ ~2~

Input

4
1 2 3 4

Output

1 2 4

Giải thích

Ví dụ ~1~

Chọn ~l=1~ và ~r=2~ thì ~S_1=5~, ~S_2=4~, nên ~|S_1-S_2|=1~.

Ví dụ ~2~

Chọn ~l=2~ và ~r=4~ thì ~S_1=3~, ~S_2=4~, nên ~|S_1-S_2|=1~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 10^6~.
• ~1 \le a_i \le 10^9~.

Gợi ý

Tính tổng tiền tố và hậu tố. Dùng hai con trỏ vì khi tăng ~l~ thì ~S_1~ tăng, khi giảm ~r~ thì ~S_2~ tăng.

Cho một tờ giấy ô vuông kích thước ~n \times m~. Cần cắt một đường xoắn ốc trên các đường lưới.

Quy trình cắt như sau:

• Bắt đầu từ mép dưới của tờ giấy, trên đường lưới thẳng đứng cách mép trái đúng ~1~ ô.
• Ban đầu cắt theo hướng lên, từng đoạn đơn vị một.
• Tiếp tục cắt thẳng theo hướng hiện tại cho đến khi đoạn cắt tiếp theo sẽ làm phần giấy hiện tại tách thành hai phần.
• Khi đó đổi hướng theo thứ tự lên, phải, xuống, trái, rồi lặp lại.
• Dừng lại khi sau một lần đổi hướng không còn đoạn nào có thể cắt tiếp.

Yêu cầu

Tính tổng độ dài các đoạn cắt cần thực hiện.

Dữ liệu

Dòng duy nhất chứa hai số nguyên ~n~ và ~m~.

Kết quả

In ra một số nguyên là tổng độ dài các đoạn cắt.

Ví dụ

Ví dụ ~1~

Input

3 3

Output

4

Ví dụ ~2~

Input

3 4

Output

6

Giải thích

Ví dụ ~1~

Tổng độ dài đường cắt là ~4~.

Ví dụ ~2~

Tổng độ dài đường cắt là ~6~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n, m \le 10^9~.

Gợi ý

Không cần mô phỏng. Độ dài đường cắt luôn bằng số ô bên trong sau phép đối ngẫu, tức ~(n-1)(m-1)~.

Cho một bảng kích thước ~n \times m~. Mỗi ô là ô trống hoặc tường. Có đúng một ô bắt đầu ký hiệu s và đúng một ô đích ký hiệu f.

Có thể di chuyển giữa hai ô trống kề nhau theo cạnh. Ô s và ô f cũng được xem là ô trống. Có thể đi qua một ô nhiều lần.

Nhiệt độ thay đổi như sau:

• Mỗi lần di chuyển theo chiều ngang, nhiệt độ giảm ~1~.
• Mỗi lần di chuyển theo chiều dọc, nhiệt độ tăng ~1~.

Chỉ xét độ chênh lệch giữa nhiệt độ ban đầu và nhiệt độ khi đến ô f.

Yêu cầu

Tìm độ chênh lệch nhỏ nhất có thể giữa nhiệt độ ban đầu và nhiệt độ cuối cùng. Nếu không thể đi từ s đến f, in ra ~-1~.

Dữ liệu

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự thuộc tập . , # , s , f.

Kết quả

Nếu không thể thoát khỏi ngôi nhà, in ra ~-1~.

Ngược lại, in ra một số nguyên không âm là độ chênh lệch nhỏ nhất có thể.

Ví dụ

Ví dụ ~1~

Input

4 3
..f
..#
s##
...

Output

0

Giải thích

Ví dụ ~1~

Có thể đi lên ~2~ lần rồi sang phải ~2~ lần. Nhiệt độ tăng ~2~ rồi giảm ~2~, nên chênh lệch cuối cùng bằng ~0~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, m \le 1000~.
• Bảng chứa đúng một ký tự s và đúng một ký tự f.

Gợi ý

DFS/BFS kiểm tra ~s~ đến được ~f~. Nếu trong thành phần đi được có cả khả năng đi ngang và đi dọc để tạo vòng điều chỉnh nhiệt, đáp án là parity của khoảng cách Manhattan; ngược lại là chính khoảng cách Manhattan.

Cho một dải ô vuông, mỗi ô có màu đỏ hoặc xanh. Dải được mô tả bằng xâu ~s~ gồm các ký tự R và B.

Hai người chơi luân phiên đi. Ở mỗi lượt, người chơi chọn một dải mà màu của ô đầu tiên và ô cuối cùng khác nhau, rồi cắt dải đó thành hai dải có độ dài nguyên dương. Người không còn nước đi sẽ thua.

Bill đi trước.

Yêu cầu

Xác định Bill có thắng khi cả hai người đều chơi tối ưu hay không.

Dữ liệu

Dòng duy nhất chứa xâu ~s~.

Kết quả

In ra Win nếu Bill thắng, ngược lại in ra Lose.

Ví dụ

Ví dụ ~1~

Input

RB

Output

Win

Ví dụ ~2~

Input

BRB

Output

Lose

Giải thích

Ví dụ ~1~

Bill cắt dải thành hai dải độ dài ~1~. Sau đó không còn dải nào có hai đầu khác màu, nên người chơi tiếp theo không có nước đi.

Ví dụ ~2~

Hai đầu của dải ban đầu cùng màu, nên Bill không có nước đi.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le |s| \le 100000~.
• ~s~ chỉ gồm các ký tự R và B.

Gợi ý

Nếu hai đầu xâu cùng màu thì Bill không đi được và thua. Nếu khác màu, Bill luôn cắt được thành hai dải đều có hai đầu cùng màu, nên thắng.

Có ~n~ người, được đánh số từ ~1~ đến ~n~. Ban đầu, thứ tự trong hàng là hoán vị ~a_1, a_2, \ldots, a_n~. Cần biến đổi hàng thành hoán vị ~b_1, b_2, \ldots, b_n~.

Một thao tác tái sắp xếp được thực hiện như sau:

• Chọn một tập con không rỗng các người.
• Những người được chọn rời khỏi hàng.
• Họ đứng vào đầu hàng theo thứ tự ngược lại so với thứ tự xuất hiện của họ trong hàng trước thao tác.
• Những người không được chọn giữ nguyên thứ tự tương đối.

Cần tìm không quá ~15~ thao tác để đạt được thứ tự mong muốn. Không cần tối thiểu hóa số thao tác. Đề bài đảm bảo luôn tồn tại lời giải với không quá ~15~ thao tác.

Yêu cầu

In ra một dãy không quá ~15~ thao tác biến đổi hoán vị ~a~ thành hoán vị ~b~.

Dữ liệu

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa hoán vị ~a_1, a_2, \ldots, a_n~.
• Dòng thứ ba chứa hoán vị ~b_1, b_2, \ldots, b_n~.

Kết quả

• Dòng thứ nhất in số nguyên ~k~ là số thao tác tìm được.

• Trong ~k~ dòng tiếp theo, dòng thứ ~i~ mô tả một thao tác:

  • Đầu tiên in số nguyên ~c_i~ là số người được chọn.
  • Sau đó in ~c_i~ số nguyên phân biệt là số hiệu những người được chọn.

Các số hiệu trong cùng một thao tác có thể in theo thứ tự bất kỳ.

Ví dụ

Ví dụ ~1~

Input

5
5 4 3 2 1
3 4 5 1 2

Output

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

Ví dụ ~2~

Input

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

Output

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

Giải thích

Ví dụ ~1~

Thứ tự thay đổi như sau:

~5,4,3,2,1 \rightarrow 1,2,3,4,5 \rightarrow 5,1,2,3,4 \rightarrow 4,5,1,2,3 \rightarrow 3,4,5,1,2~.

Ví dụ ~2~

Thứ tự thay đổi như sau:

~3,4,7,6,2,5,1 \rightarrow 5,6,7,3,4,2,1 \rightarrow 4,3,5,6,7,2,1 \rightarrow 2,6,3,4,5,7,1~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10000~.
• ~a~ và ~b~ là hai hoán vị của các số từ ~1~ đến ~n~.
• Luôn tồn tại lời giải dùng không quá ~15~ thao tác.

Gợi ý

Quy về biến hoán vị đơn vị thành hoán vị đích. Chia đôi hoán vị đích, xử lý đệ quy hai nửa song song, rồi dùng một thao tác cuối để đưa nửa đầu lên trước và đảo đúng thứ tự.