Cho xâu ~S~ gồm các kí tự trong bảng chữ cái từ ~a~ tới ~z~ có độ dài ~n~.

Cho ~q~ truy vấn, mỗi truy vấn có dạng ~(x,y,u,v)~, hỏi hai xâu ~S[x:y]~ và ~S[u:v]~ có bằng nhau không? Biết ~y - x = v - u~.

Input

• Dòng đầu là hai số nguyên dương ~n~ và ~q~ miêu tả độ dài xâu và số truy vấn ~(1 \le n,q \le 1 \times 10^6)~.
• Dòng hai gồm xâu ~S~.
• ~q~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~(x,y,u,v)~ ~(1 \le x \le y \le n; 1 \le u \le v \le n)~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, nếu chúng bằng nhau in ra ~1~, ngược lại in ra ~0~ theo từng dòng.

Sample Input 1

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

Sample Output 1

1
0
1

Cho 2 xâu ~S~ và ~T~. Đếm số lần xuất hiện của ~T~ trong ~S~ (có bao nhiêu xâu con liên tiếp của ~S~ bằng ~T~).

Input

• Dòng đầu tiên là xâu ~S~.
• Dòng thứ hai là xâu ~T~.

Output

• Số lần xuất hiện của ~T~ trong ~S~.

Điều kiện

• ~1 \le |T| \le |S| \le 10^6~.

Ví dụ

Input:

asasa
asa

Output:

2

Cho xâu ~S~ độ dài ~n~ chỉ chứa các chữ cái tiếng Anh viết thường. Tìm xâu ~T~ ngắn nhất sao cho khi viết lặp lại ~T~ cho đến khi đủ ~n~ kí tự thì được xâu ~S~.

Input

• Một dòng duy nhất là xâu ~S~.

Output

• In ra ~T~.

Điều kiện

• ~1 \le |S| \le 10^5~.

Ví dụ

Input:

sussussu

Output:

sus

Cho xâu ~S~ gồm các kí tự trong bảng chữ cái từ ~a~ tới ~z~ có độ dài ~n~.

Hãy in ra xâu con liên tiếp dài nhất của ~S~ sao cho nó là một palindrome.

Input

• Gồm xâu ~S~. ~|S| \le 10^6~.

  Output

• In ra xâu con liên tiếp dài nhất là palindrome.

Sample Input 1

aybabtu

Sample Output 1

bab

Cho ~n~ xâu kí tự, đây được gọi là ~n~ xâu "dữ liệu".

Bạn cần trả lời ~m~ câu hỏi có dạng như sau:

• Cho xâu ~s~, hãy xác định xem có tồn tại xâu kí tự trong ~n~ xâu dữ liệu được cho thỏa mãn nó có chung độ dài và khác xâu ~s~ ở đúng một vị trí.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n,m~.
• ~n~ dòng sau, mỗi dòng gồm một xâu kí tự miêu tả các xâu dữ liệu.
• ~m~ dòng sau, mỗi dòng gồm một xâu kí tự miêu tả truy vấn.
• Các xâu trong Input đều chỉ chứa ba kí tự ~'a','b','c'~.

Constraints

• ~1 \le n,m \le 3\times10^5~
• Độ dài các xâu được cho không quá ~6 \times 10^5~.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~n,m,|s| \le 100~
• Subtask ~1~ (~30\%~ số điểm): ~n,m,|s| \le 2000~
• Subtask ~2~ (~40\%~ số điểm): Không ràng buộc gì thêm.

Output

• Với mỗi truy vấn, in ra "YES" nếu tồn tại xâu thỏa mãn, ngược lại in ra "NO".

Sample Input 1

2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

Sample Output 1

YES
NO
NO

Một xâu xoay được tạo ra bởi chuyển một chữ cái từ cuối lên đầu xâu. Ví dụ, các xâu xoay của ~marisa~ là ~marisa, amaris, samari, isamar, risama~ và ~arisam~.

Hãy xác định xâu xoay có thứ tự từ điển nhỏ nhất của xâu ~S~ cho trước.

Input

• Gồm một dòng chứa xâu ~s~.

Constraints

• ~1 \le |s| \le 10^6~

Subtask:

• Subtask ~1~ (~50\%~ số điểm): ~n \le 10^3~
• Subtask ~2~ (~50\%~ số điểm): ~n \le 10^6~

Output

• In ra xâu có thứ tự từ điển nhỏ nhất.

Sample Input 1

marisa

Sample Output 1

amaris

Cho một bảng hình chữ nhật có ~N~ dòng và ~M~ cột gồm các chữ cái in thường từ ~'a'~ đến ~'z'~. Bảng này có tính chất: ở mỗi cột, khi ghép các kí tự từ trên xuống dưới sẽ thu được một xâu đại diện và trong bảng các xâu đại diện là đôi một khác nhau.

Yêu cầu: Hãy tìm cách xoá nhiều nhất các dòng (lần lượt từ dòng đầu tiên xuống dưới) của bảng để thu được một bảng mới vẫn đảm bảo tính chất trên. (Chỉ được xoá tối đa ~N-1~ dòng)

Dữ liệu nhập vào từ file văn bản DELROW.INP:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ cách nhau một dấu cách~;~
• ~N~ dòng sau, mỗi dòng chứa một xâu có dộ dài ~M.~

Kết quả ghi ra file văn bản DELROW.OUT:

Gồm một số duy nhất là kết quả của bài toán.

Ví dụ

Input

5 4
qwpt
abcf
bvoa
abka
bbhb

Output

2

Giải thích:

Xoá tối đa ~2~ dòng đầu. Nếu xoá cả dòng thứ ~3~ thì cột đầu tiên và cột cuối cùng sẽ giống nhau. (không thoả mãn tính chất của bảng)

Giới hạn

• Có ~40\%~ số test tương ứng với số điểm có ~N,M≤100;~
• ~30\%~ số test khác tương ứng với số điểm có ~N,M≤500;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N,M≤5000.~

Cho một xâu nhị phân S độ dài ~n~ (các chỉ số được đánh số từ ~1~) và ~q~ truy vấn thuộc một trong hai loại:

• ~1 \; u \; x~: Gán ~S_u = x~, trong đó ~x \in \{0, 1\}~.
• ~2 \; u \; v \;x~: Kiểm tra xem hai xâu ~S[u..u+x-1]~ và ~S[v..v+x-1]~ có bằng nhau không. Nói cách khác, kiểm tra xem hai xâu con liên tiếp độ dài ~x~ bắt đầu từ ~u~ và ~v~ có bằng nhau không?

Với mỗi truy vấn ~2~, hãy in ra ~1~ nếu hai xâu bằng nhau, ~0~ là ngược lại.

Input

• Dòng đầu tiên gồm xâu ~S~ có độ dài ~n~.
• Dòng thứ hai gồm số nguyên ~q~ - số truy vấn.
• ~q~ dòng sau, mỗi dòng là ba hoặc bốn số nguyên dương thuộc một trong hai loại như miêu tả trên.

Constraints

• ~1 \le n, q \le 2 \times 10^5~
• ~1 \le u + x - 1, v + x - 1 \le n~

Subtasks

• Subtask ~1~ ~(30\%)~: ~1 \le n, q \le 3000~.
• Subtask ~2~ ~(70\%)~: Không còn điều kiện gì thêm.

Output

• Gồm một xâu nhị phân gồm ~q~ kí tự ~0~ và ~1~.

Sample Input 1:

1000100
3
2 1 5 3
1 3 1
2 1 3 3

Sample Output 1:

11

Explanation 1:

Truy vấn đầu tiên có ~S[1..3] = 100~, ~S[5..7] = 100~. Truy vấn thứ hai xâu ~S~ trở thành ~1010100~ Truy vấn thứ ba có ~S[1..3] = 101~, ~S[3..5] = 101~.

Gọi ~S(l,r,a)~ là Set của các phần tử từ ~l~ tới ~r~ trong mảng ~a~. Ví dụ, nếu ~a = [1,1,1,3,3,2]~ thì ~S(1,6, a) = [1,2,3]~; ~S(4,6,a) = [2,3]~.

Cho hai mảng các số nguyên dương ~a~ và ~b~ có kích thước là ~n~. Bạn có ~q~ truy vấn, truy vấn thứ ~i~ cho bốn số ~l_i~, ~r_i~ và ~x_i~, ~y_i~. Với mỗi truy vấn, hãy kiểm tra xem ~S(l_i,r_i,a)~ có bằng với ~S(x_i,y_i,b)~ hay không.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~1 \leq n, q \leq 2 \cdot 10^5~).

• Dòng tiếp theo chứa ~n~ số nguyên dương là các phần tử mảng ~a~ (~1 \leq a_i \leq 10^9~).

• Dòng tiếp theo chứa ~n~ số nguyên dương là các phần tử mảng ~b~ (~1 \leq b_i \leq 10^9~).

• ~q~ dòng tiếp, dòng thứ ~i~ chứa ~4~ số nguyên dương ~l_i~, ~r_i~ và ~x_i~, ~y_i~ (~1 \leq l_i \leq r_i \leq n~, ~1 \leq x_i \leq y_i \leq n~).

Output

• In ra ~q~ dòng, nếu ~S(l_i,r_i,a)~ bằng với ~S(x_i,y_i,b)~ in ra ~\textbf{YES}~, ngược lại in ra ~\textbf{NO}~.

Scoring

Sample Input 1

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

Sample Output 1

YES
YES
NO
YES
NO

Cho hai dãy số nguyên ~a_1,a_2,...,a_n~ và ~b_1,b_2,...,b_n~. Bạn cần sử dụng thao tác sau đúng một lần:

• Chọn hai chỉ số ~[L,R]~ thỏa mãn ~1 \le L \le R \le n~ và hoán đổi vị trí hai dãy con ~a_L,a_{L+1},...,a_R~ với ~b_L,b_{L+1},...,b_R~.

Hãy đếm số cách thực hiện thao tác trên sao cho sau khi thực hiện, ít nhất một trong hai dãy ~a~ hoặc ~b~ trở thành hoán vị của các số từ ~1~ đến ~n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy ~b~.

Constraints

• ~2 \le n \le 2*10^5~

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~2~ (~40\%~ số điểm): ~n \le 5000~
• Subtask ~3~ (~30\%~ số điểm): Không ràng buộc gì thêm.

Output

• In ra số cách thực hiện thao tác trên.

Sample Input 1

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

Sample Output 1

8

Phát có một ma trận kích thước ~n \times m~, mỗi ô chứa một chữ cái in thường. Phát đánh số các hàng từ ~1~ đến ~n~, từ trên xuống dưới, và các cột từ ~1~ đến ~m~, từ trái sang phải.

Một ma trận được gọi là đối xứng nếu mọi hàng và cột của nó đều là một xâu đối xứng. Một xâu là xâu đối xứng nếu đọc từ trái sang phải hay ngược lại đều cho kết quả giống nhau.

Một ma trận được gọi là gần đối xứng nếu tồn tại một cách sắp xếp lại các kí tự trên các hàng sao cho bảng tạo thành là một bảng đối xứng. Lưu ý rằng các hàng là độc lập với nhau và chỉ có thể sắp xếp lại các kí tự trên cùng một hàng. Một ma trận đối xứng cũng là một ma trận gần đối xứng.

Yêu cầu: Hãy giúp Phát đếm xem có bao nhiêu ma trận con của ma trận ~n \times m~ là một ma trận gần đối xứng. Cụ thể hơn, bạn cần đếm số bộ ~(x_1, x_2, y_1, y_2)~ thỏa mãn ~1 \leq x_1 \leq x_2 \leq n~, ~1 \leq y_1 \leq y_2 \leq m~ sao cho ma trận con có góc trái trên ~(x_1, y_1)~ và góc phải dưới ~(x_2, y_2)~ là một ma trận gần đối xứng.

Input

• Dòng đầu tiên chứa hai số nguyên ~m~ và ~n~ cách nhau bởi dấu cách, là kích thước của ma trận (~1 \leq n, m \leq 300~).
• ~n~ dòng tiếp theo mô tả bảng hiện tại của Alice, dòng thứ ~i~ chứa một xâu ~m~ kí tự, trong đó kí tự thứ ~j~ là chữ cái ở ô ~(i, j)~.

Output

• Một số nguyên duy nhất là số ma trận con gần đối xứng.

Subtask

• Có ~30\%~ số test ứng với 30% số điểm của bài thỏa mãn ~n = 1~.
• ~30\%~ số test khác ứng với 30% số điểm của bài thỏa mãn ~m, n \leq 30~.
• ~20\%~ số test khác ứng với 30% số điểm của bài thỏa mãn ~m, n \leq 100~.
• ~20\%~ số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Example

Input 1

1 3
aba

Output 1

4

Input 2

2 3
aca
aac

Output 2

11

Input 3

3 5
accac
aaaba
cccaa

Output 3

43

Alice là kỹ sư phát triển nền tảng mạng xã hội VOI giúp cho cộng đồng lập trình viên tương tác với nhau. Có ~N~ bài đăng được đánh số từ ~1~ đến ~N~ theo trình tự thời gian đăng bài. Alice phân loại các bài đăng theo chủ đề, bài đăng thứ ~i~ ~(1 \le i \le N)~ có chủ đề là ~A_i~.

Alice định nghĩa một đoạn ~[L, R]~ gồm các bài đăng liên tiếp từ chỉ số ~L~ đến chỉ số ~R~ ~(1 \le L \le R \le N)~ là toàn vẹn nếu với mỗi chủ đề ~t~, hoặc không có bài nào có chủ đề ~t~ nằm trong đoạn ~[L, R]~ hoặc tất cả các bài có chủ đề ~t~ đều nằm trong đoạn này.

Yêu cầu: Vào dịp Noel, Alice công bố dữ liệu chủ đề của ~N~ bài đăng và mở cuộc thi trên VOI cho các lập trình viên tham gia. Alice lần lượt đưa ra ~Q~ truy vấn, mỗi truy vấn cho biết một cặp số nguyên ~U, V~ ~(1 \le U \le V \le N)~ và yêu cầu thí sinh đếm số đoạn ~[L, R]~ là toàn vẹn với ~U \le L \le R \le V~.

Cụ thể, với mỗi truy vấn, cần đếm xem có bao nhiêu cặp ~L, R~ thỏa mãn:

• ~U \le L \le R \le V~;

• Không tồn tại hai giá trị ~i, j~ nào sao cho:

  • ~(1 \le i < L)~ hoặc ~(R < i \le N)~;

  • ~L \le j \le R~;

  • ~A_i = A_j~.

Input

Vào từ file văn bản POST.INP:

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_1, A_2, \ldots, A_N \le 10^9)~.

• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~U~ và ~V~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản POST.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số là đáp án cho truy vấn tương ứng.

Scoring

Sample Input 1

7 2
1 2 2 3 1 6 3
1 7
2 6

Sample Output 1

3
2

Notes

• Truy vấn 1, có 3 đoạn toàn vẹn:

$$[1,7], [2,3], [6,6]$$

• Truy vấn 2, có 2 đoạn toàn vẹn:

$$[2,3], [6,6]$$

Với hai xâu ~S~ và ~T~ chỉ gồm các chữ cái Latin thường, ta nói ~T~ là ~S~-đẹp nếu ~S~ là một xâu con liên tiếp của ~T~.

Ví dụ, với ~S = \texttt{xya}~ và ~T = \texttt{xxyaay}~, xâu ~T~ là ~S~-đẹp.

Cho một danh sách ~L~ gồm ~n~ xâu ký tự. Có ~q~ thao tác thuộc một trong ba loại:

• i S: thêm xâu ~S~ vào danh sách ~L~. Nếu ~S~ đã xuất hiện trong ~L~, xâu ~S~ vẫn được thêm như một phần tử mới.
• e S: xóa một lần xuất hiện của xâu ~S~ khỏi danh sách ~L~. Dữ liệu đảm bảo ~S~ đang xuất hiện trong ~L~.
• q S: đếm số lượng xâu ~S~-đẹp trong danh sách ~L~.

Với mỗi thao tác loại q, hãy in ra kết quả tương ứng.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu trong danh sách ban đầu ~L~.
• Dòng tiếp theo chứa số nguyên dương ~q~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một thao tác theo định dạng c S, trong đó ~c~ là một trong ba ký tự i, e, q.

Output

• Với mỗi thao tác dạng q S, in ra một dòng là số lượng xâu trong danh sách hiện tại chứa ~S~ như một xâu con liên tiếp.

Ràng buộc

• ~1 \le n, q \le 5 \cdot 10^5~
• Mỗi xâu chỉ gồm các chữ cái Latin thường từ a đến z.
• Tổng độ dài tất cả các xâu xuất hiện trong input không vượt quá ~5 \cdot 10^5~.
• Với thao tác e S, dữ liệu đảm bảo xâu ~S~ đang có trong danh sách.

Subtask

Sample Input

3
aaaa
babbbb
aaaa
4
q a
e aaaa
i xxyaay
q aa

Sample Output

3
2

Giải thích

Ban đầu danh sách gồm:

~[\texttt{aaaa}, \texttt{babbbb}, \texttt{aaaa}]~

• Với truy vấn q a, cả ba xâu đều chứa a, nên đáp án là ~3~.
• Sau thao tác e aaaa, danh sách còn một xâu aaaa và một xâu babbbb.
• Sau thao tác i xxyaay, danh sách có thêm xâu xxyaay.
• Với truy vấn q aa, hai xâu chứa aa là aaaa và xxyaay, nên đáp án là ~2~.