Radar theo dõi các loài sinh vật biển đã gặp vấn đề! Một radar bị lỗi khi ít nhất 1 trường hợp dưới đây xảy ra:

• Đầu hoặc đuôi sinh vật biển này ở trong đầu hoặc đuôi sinh vật khác.
• Sinh vật biển có đầu nhưng không có đuôi hoặc ngược lại.

Mỗi radar được biểu diễn bằng 1 xâu chỉ gồm 3 loại ký tự H, T, . lần lượt ký hiệu cho đầu, đuôi sinh vật biển và . là khoảng không. Mọi sinh vật hiển thị trên một radar nằm ngang và chỉ theo 1 trong 2 chiều nhất định: H...T hoặc T...H (phần đầu trước, phần đuôi sau và ngược lại). Trong trường hợp 1 radar có nhiều cách hiểu khác nhau, ưu tiên cách hiểu mà trong đó radar không gặp lỗi (xem test ví dụ để hiểu rõ hơn). Ví dụ: H....T.......THHT là hình ảnh của 1 radar hợp lệ. H....TH...T....H là hình ảnh của 1 radar bị lỗi.

Yêu cầu

Cho ~n~ radar, hãy xác định mỗi radar có gặp lỗi hay không.

Dữ liệu

• Dòng đầu tiên chứa số nguyên ~n~ là số lượng radar cần truy vấn ~(1 \leq n \leq 10^5)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa xâu ~s_i~ đại diện cho radar thứ ~i~ ~(|s_i| \leq 100)~. Đảm bảo xâu ~s~ chỉ chứa các ký tự H, T hoặc ..

Kết quả

• In ra ~n~ dòng, dòng thứ ~i~ in ra YES nếu radar thứ ~i~ gặp lỗi, ngược lại in ra NO.

Ví dụ

Input

5
...H...H.T...T...
...H...T...H.T...
...T...H...T...
T...H...H...T...
...HH...T...T...

Output

YES
NO
YES
NO
YES

Giải thích

TH1: Radar gặp lỗi vì đầu/đuôi của 1 sinh vật nằm trong đầu/đuôi của 1 sinh vật khác.

TH2: Radar có hai cách hiểu: ...H_1...T_1...H_2.T_2... hoặc ...H_1...T_2...H_2.T_1... Trong đó, cách hiểu đầu tiên cho kết quả radar không bị lỗi → Cách hiểu này được ưu tiên và đáp án là NO.

TH3: Có một sinh vật biển có đuôi nhưng không có đầu.

Cho dãy DNA được biểu diễn bằng xâu ~s~ chỉ chứa các ký tự A, T, G, C. Đặc điểm nổi trội nhất của DNA là xâu con dài nhất xuất hiện ít nhất 2 lần trong xâu ~s~.

Yêu cầu

Cho dãy DNA được biểu diễn bởi xâu ~s~, xuất ra đặc điểm nổi trội của DNA.

Nếu có nhiều xâu con thỏa mãn, xuất ra xâu con có vị trí xuất hiện đầu tiên là trái nhất.

Dữ liệu

Gồm một dòng duy nhất chứa xâu ~s~ ~(|s| ≤ 10^5)~ chỉ gồm các ký tự A, T, G, C.

Kết quả

Gồm 1 dòng duy nhất là xâu con của ~s~ theo yêu cầu đề bài.

Ví dụ

Sample Input 1

ATATA

Sample Output 1

ATA

Giải thích

Trong các xâu con xuất hiện ít nhất 2 lần: A, T, AT, TA, ATA; xâu con ATA có độ dài lớn nhất.

Sample Input 2

ATTAC

Sample Output 2

A

Giải thích

Trong các xâu con xuất hiện ít nhất 2 lần: A, T; xâu con A có độ dài lớn nhất và vị trí xuất hiện đầu tiên của A ở phía trái nhất → A là kết quả bài toán.

Yêu cầu

Cho ~t~ truy vấn, mỗi truy vấn chứa một xâu ~s~ độ dài ~n~. Với mỗi truy vấn, hãy tìm số lượng kí tự ít nhất để thêm vào sau xâu ~s~ để tạo thành một palindrome.

Dữ liệu

• Dòng đầu tiên chứa số ~t~ - số truy vấn cần trả lời ~(1 \le t \le 100)~.
• Mỗi dòng trong ~t~ dòng tiếp theo chứa một xâu ~s~.
• Tổng độ dài các xâu không quá ~2 \times 10^5~.

Kết quả

• Với mỗi truy vấn, in ra trên cùng một dòng là số lượng kí tự ít nhất cần thêm vào và xâu ~s~ sau khi thêm những kí tự ấy.

Ví dụ

Sample Input

4
aaaa
educontest
xyz
abcdefghg

Sample Output

0 aaaa
9 educontestsetnocude
2 xyzyx
6 abcdefghgfedcba

Cho xâu ~S~ có độ dài ~n (n \leq 10^5)~ chỉ gồm các chữ cái tiếng Anh in thường. Ký tự thứ ~i~ trong xâu được ký hiệu là ~S_i \ (i \leq n)~. Có 2 loại truy vấn trên xâu ~S~ như sau:

• ~1\ p\ c~: Thực hiện phép gán ~S_p = c~.
• ~2\ x\ y\ u\ v~: So sánh thứ tự từ điển của 2 xâu con ~S[x...y]~ và ~S[u...v]~.

Định nghĩa về thứ tự từ điển của 2 xâu:

• ~A=B~ khi: ~|A|=|B|~ (trong đó ~|T|~ là độ dài của xâu ~|T|~) và ~A_i = B_i (\forall i: 1 \leq i \leq |A|)~.
• ~A<B~ (hay ~B>A~) khi ~A~ là xâu con tiền tố của ~B~ hoặc ~A_k < B_k~ (với ~k~ là vị trí đầu tiên mà ~A_k \neq B_k~).

Yêu cầu

Cho ~q~ truy vấn thuộc 1 trong 2 dạng trên. Với truy vấn loại 2, in ra:

• -1 nếu ~S[x...y]<S[u...v]~</li>
• 0 nếu ~S[x...y]=S[u...v]~
• 1 nếu ~S[x...y]>S[u...v]~

Dữ liệu

• Dòng đầu chứa ~2~ số nguyên dương ~n,q (n,q \leq 10^5)~.
• Dòng tiếp theo chứa ~n~ chữ cái tiếng Anh in thường biểu diễn xâu ~S~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc 1 trong 2 dạng:
  • ~1\ p\ c\ (1 \leq p \leq n;\ c\ \in ['a'...'z']).~
  • ~2\ x\ y\ u\ v\ (1 \leq x,y,u,v \leq n;\ x\leq y;\ u\leq v ).~

Kết quả

Với mỗi truy vấn loại 2, in cách dòng 1 số nguyên duy nhất là đáp án cho truy vấn tương ứng theo yêu cầu đề bài.

Ví dụ

Sample Input

6 5
ababac
2 1 3 3 5
2 1 2 3 5
1 5 d
2 1 3 3 5
2 4 6 2 3

Sample Output

0
-1
-1
1

Giải thích

• Truy vấn 1: "aba" = "aba"
• Truy vấn 2: "ab" < "aba"
• Truy vấn 3: S = "ababdc"
• Truy vấn 4: "aba" < "abd"
• Truy vấn 5: "bdc" > "ba"

Một chuỗi t được gọi là Chuỗi Em bé của chuỗi s khi thỏa mãn cả 3 điều kiện sau:

• ~t~ là tiền tố của ~s~;
• ~t~ là hậu tố của ~s~;
• ~t~ xuất hiện trong ~s~ nhiều hơn ~3~ lần.

1. Tiền tố của chuỗi s có độ dài ~l~ ~(1 \leq l \leq |s|)~ là chuỗi con bắt đầu tại vị trí ~0~ và kết thúc tại vị trí ~l - 1~.
2. Hậu tố của chuỗi s có độ dài ~l~ ~(1 \leq l \leq |s|)~ là chuỗi con bắt đầu tại vị trí ~|s| - l~ và kết thúc tại ~|s| - 1~.

Yêu cầu

• Cho một chuỗi ~s~, độ dài ~|s|~, và ~q~ truy vấn ~l_1,l_2,...,l_q~.
• Đối với mỗi truy vấn ~l_i~, bạn phải kiểm tra xem tiền tố của ~s~ có độ dài ~l_i~ có phải là Chuỗi Em bé của ~s~ không và đếm số lần xuất hiện của tiền tố này trong ~s~.

Dữ liệu

• Dòng đầu tiên chứa chuỗi ~s~ ~(1 \leq |s| \leq 10^5)~. Chuỗi chỉ bao gồm các chữ cái tiếng Anh in hoa.
• Dòng thứ hai của đầu vào chứa số nguyên dương ~q~, ~(1 \leq q \leq 10^5)~ là số lượng truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~l_i~, ~(1 \leq l_i \leq |s|)~.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~. Với truy vấn thứ ~i~, nếu tiền tố độ dài ~l_i~ của ~s~ là Chuỗi Em bé của ~s~ thì in YES và in số lần xâu con đó xuất hiện trong chuỗi ~s~; ngược lại, in NO.

Ví dụ

Sample Input

AAACMMTACMAA
4
1
2
3
4

Sample Output

YES 6
YES 3
NO
NO

Giải thích

• Xâu con A là Chuỗi Em bé và xuất hiện 6 lần.
• Xâu con AAA không là Chuỗi Em bé vì AAA không phải hậu tố của ~s~.

Cho xâu ~S~ có độ dài ~n \ (n \leq 5000)~ chỉ gồm các chữ cái tiếng Anh in thường và một số nguyên dương ~m~.

Một xâu a có độ dài ~n_1 \ (n_1 \leq n)~ được gọi là xâu tiền tố của ~S~ nếu như a trùng với xâu được tạo bởi ~n_1~ ký tự đầu tiên của ~S~.

Từ xâu ~S~, ta có thể tạo được xâu mới bằng cách thêm tiền tố ~a~ của ~S~ vào cuối xâu ~S~, thao tác này có thể được thực hiện nhiều lần.

Yêu cầu

Đếm số xâu phân biệt độ dài ~m \ (m \geq n)~ có thể tạo ra từ xâu ~S~ ban đầu, in ra kết quả là phần dư khi chia cho ~10^9 + 7~.

Dữ liệu

• Dòng thứ nhất gồm 2 số nguyên dương ~n~ và ~m \ (n \leq m \leq 5000)~.
• Dòng thứ hai gồm một xâu ~S~ có độ dài ~n~.

Kết quả

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Sample Input

5 8
baacb

Sample Output

4

Giải thích

Với xâu ~S = ~ baacb, các xâu có thể tạo ra có độ dài ~m = 8~ là:

• baacbbbb
• baacbbba
• baacbbab
• baacbbaa

Cho dãy số nguyên F được cho bởi công thức truy hồi sau:

• ~F_1 = a~ và ~F_2 = b~.
• ~\forall t>2: F_t = F_{t-1} + F_{t-2}~.

Dãy số nguyên ~S = S_1, S_2, ..., S_n~

Trong một phép biến đổi, bạn có thể chọn ~\textbf{1}~ phần tử trong dãy ~F~ và tăng hoặc giảm nó ~1~ đơn vị.

Yêu cầu

Với mỗi ~x~ từ ~1~ đến ~k~, nếu được thực hiện chính xác ~x~ phép biến đổi một cách tối ưu, tìm số lần nhiều nhất có thể mà dãy ~S~ xuất hiện như một dãy con liên tiếp của dãy ~F~.

Chú ý rằng những lần xuất hiện của dãy ~S~ trong dãy ~F~ sau biến đổi có thể chồng chéo nhau (tham khảo test ví dụ để rõ hơn).

Dữ liệu

• Dòng đầu chứa hai số nguyên ~a, b \ (|a|, |b| \leq 10^9)~ - hai phần tử đầu tiên của dãy truy hồi ~F~.
• Dòng thứ hai chứa hai số nguyên ~n, k \ (1 \leq n, k \leq 1000)~ - độ dài của dãy ~S~ và số phép biến đổi tối đa.
• Dòng thứ ba chứa ~n~ số nguyên ~S_i \ (|S_i| \leq 10^9)~ - các phần tử của ~S~.

Kết quả

In ra ~1~ dòng duy nhất gồm ~k~ số nguyên, số thứ ~x~ là số lần xuất hiện nhiều nhất có thể của dãy ~S~ trong dãy ~F~ sau chính xác ~x~ phép biến đổi. Nếu số lần xuất hiện có thể nhiều tùy ý thì in ~-1~.

Ví dụ

Sample Input 1

3 -2
3 6
1 -2 1

Sample Output 1

0 1 1 2 2 2

Giải thích

Dãy ~F=\{3,-2,1,-1,0,-1,-1,-2,-3,-5,...\}~.

• Khi ~x~ = ~1~: Không có cách biến đổi nào làm cho dãy ~S~ trở thành dãy con của ~F~.

• Khi ~x~ = ~2~: Biến đổi dãy ~F~ thành ~\{1,-2,1,-1,0,...\}~ (giảm phần tử đầu tiên ~2~ đơn vị). Khi đó, dãy ~S~ chính là dãy con gồm 3 phần tử đầu tiên của ~F~. Chứng minh được không có cách biến đổi nào khiến ~S~ xuất hiện nhiều hơn 1 lần trong ~F~.

• Khi ~x~ = ~5~: Biến đổi dãy ~F~ thành ~\{1,-2,1,-2,1,-1,0,-2,-3,-5,...\}~. Khi đó, ~S~ xuất hiện đúng 2 lần trong ~F~ (dãy con bắt đầu tại vị trí ~1~ và vị trí ~3~). Chứng minh được không có cách biến đổi nào khiến ~S~ xuất hiện nhiều hơn 2 lần trong ~F~.

Sample Input 2

0 0
1 2
0

Sample Output 2

-1 -1

Giải thích

Dãy ~S = \{0\}~. Dãy ~F = \{0, 0, 0, 0,...\}~

Với ~x=1~ và ~x=2~, tồn tại cách biến đổi ~F~ để dãy ~S~ xuất hiện vô số lần trong dãy ~F~.

Cho xâu ~S~ có độ dài ~n \ (n \leq 10^4)~ chỉ gồm các chữ cái tiếng Anh in thường. Một xâu con của ~S~ là một chuỗi các ký tự liên tiếp trong ~S~.

Hai xâu ~A~ và ~B~ được cho là riêng biệt nếu tồn tại bất kỳ vị trí ~i~ sao cho ~A_i \neq B_i \ (1 \leq i \leq n)~.

Yêu cầu

Đếm số lượng xâu con đôi một riêng biệt của ~S~.

Dữ liệu

• Dòng thứ nhất gồm số nguyên dương ~n \ (n \leq 10^4)~.
• Dòng thứ hai gồm một xâu ~S~ có độ dài ~n~.

Kết quả

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Sample Input 1

4
baab

Sample Output 1

8

Giải thích

Với xâu S = baab, các xâu con đôi một riêng biệt có thể tạo ra là: "b", "a", "ba", "aa", "ab", "baa", "aab", "baab".

Sample Input 2

10
abcxyzabbc

Sample Output 2

49

Cho ~n~ xâu kí tự và ~1~ xâu ~S~, ký tự thứ ~i~ được ký hiệu là ~S_i~ (~1\leq i\leq n~).

Có ~q~ thao tác được thực hiện trên ~S~, mỗi thao tác có dạng:

• ~(x,c)~: biến đổi tất cả kí tự của xâu ~S~ từ vị trí thứ ~x~ trở đi trở thành kí tự ~c~ (thực hiện phép gán ~S_i = c~ với mọi ~x\leq i\leq n~).

Yêu cầu

Sau mỗi thao tác, hãy in ra số lượng xâu trong mảng có thứ tự từ điển nhỏ hẳn hơn xâu ~S~.

Dữ liệu

• Dòng đầu tiên gồm hai giá trị ~n~ và ~q \ (1 \leq n, q \leq 10^6)~.
• Dòng thứ hai là xâu ~S~ với tối đa ~10^6~ ký tự là chữ cái Latin viết thường.
• ~n~ dòng tiếp theo là các xâu kí tự trong mảng, mỗi xâu chỉ chứa chữ cái Latin viết thường và tổng độ dài các xâu không vượt quá ~10^6~.
• ~q~ dòng cuối cùng là các truy vấn thay đổi dưới dạng ~(x,c)~ với ~x~ là 1 số nguyên dương (~1\leq x\leq n~) và ~c~ là 1 kí tự Latin viết thường, phân biệt bằng dấu cách.

Kết quả

• Dòng đầu tiên in kết quả bài toán trước khi có các thao tác thay đổi.
• ~q~ dòng tiếp theo, in kết quả bài toán sau mỗi thao tác thay đổi.

Ví dụ

Sample Input

4 3
anatoly
boris
anatooo
anbbbbu
anba
5 o
3 b
7 x

Sample Output

0
0
2
3

Giải thích

Thao tác 1: ~S="anatooo"~.

Thao tác 2: ~S="anbbbbb"~.

Thao tác 3: ~S="anbbbbx"~.

Cho một bảng ~A~ gồm ~M \times N~ phần tử, mỗi phần tử đều là giá trị không âm bé hơn ~2^{12}~.

Yêu cầu

Tìm một hình chữ nhật con của bảng ~A~ sao cho tổng XOR của các phần tử trong mảng là lớn nhất.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~M, N \ (M, N \leq 300)~.
• ~M~ dòng tiếp theo, chứa ~N~ số nguyên không âm là giá trị của bảng ~A \ (0 \leq A[i][j] \leq 2^{12})~.

Kết quả

Một dòng duy nhất chứa đáp án là yêu cầu của bài toán.

Ví dụ

Sample Input

2 2
1 2
3 8

Sample Output

11

Giải thích

Hình chữ nhật con có góc trái trên là ~(2,1)~ và góc phải dưới là ~(2,2)~.

Cho hai xâu ~A~ độ dài ~N~ và ~B~ độ dài ~M~.

Đối với mỗi chữ cái ~c\in['a'...'z']~, ~D_c~ được gọi là giá trị của chữ cái ~c~. Gọi độ ưng ý của 2 xâu ~A~ và ~B~ là số ~l~ lớn nhất sao cho tồn tại hai vị trí ~i,j~ thỏa mãn đẳng thức sau: $$ {\frac{D_{A_i}}{D_{B_j}} = \frac{D_{A_i} + D_{A_{i+1}}}{D_{B_j} + D_{B_{j+1}}} = \frac{D_{A_i} + D_{A_{i+1}} + D_{A_{i+2}}}{D_{B_j} + D_{B_{j+1}} + D_{B_{j+2}}} = \cdots = \frac{{\sum\nolimits_{x=0}^{l-1}} D_{A_{i+x}}}{{\sum\nolimits_{x=0}^{l-1}} D_{B_{j+x}}}} $$

Yêu cầu

Cho hai xâu ~A~ và ~B~ và mảng ~D~, hãy xác định độ ưng ý của nó.

Dữ liệu

• Dòng đầu chứa hai số là ~N~ và ~M \ (1 \leq N, M \leq 2 \times 10^5)~.
• Dòng thứ hai chứa xâu ~A~ gồm ~N~ ký tự Latin in thường.
• Dòng thứ hai chứa xâu ~B~ gồm ~M~ ký tự Latin in thường.
• Dòng thứ tư chứa mảng ~D~ gồm ~26~ số nguyên dương. Số thứ 1 là giá trị của chữ cái ~a~, số thứ 2 là giá trị của chữ cái ~b~,... ~(D_i \leq 10^9)~.

Kết quả

Gồm 1 số nguyên duy nhất là độ ưng ý của 2 xâu ~A,B~ theo miêu tả đề bài.

Ví dụ

Sample Input

6 7
aabacf
cfcferh
2 1 4 9 16 8 7 24 8 17 30 9 35 9 10 19 26 32 55 36 27 18 20 34 17 40

Sample Output

5

Giải thích

Với ~l~ = ~5~, hai vị trí ~i, j~ lần lượt là 2 và 2.