Đây là bài để nhận giveaway ~2~ giải, mỗi giải ~19.000~ VNĐ từ chúng mình.

Đề bài: Các bạn hãy đoán ba chữ số cuối cùng của kết quả Xổ số kiến thiết miền Bắc ngày 06/09/2025.

Thứ tự ưu tiên xếp giải sẽ như sau: Từ trùng khớp hoàn toàn ba chữ số cuối cùng của giải đặc biệt -> trùng khớp hoàn toàn ba chữ số cuối cùng của giải Nhất -> ... -> trùng khớp hoàn toàn hai chữ số cuối cùng của giải Bảy (với giải Bảy, chúng ta sẽ xét hai chữ số cuối cùng trong ba chữ số các bạn gửi lên hệ thống).

Nếu vẫn không tìm ra, sẽ lấy kết quả là số gần với ba chữ số cuối cùng của giải đặc biệt nhất. Nếu vẫn bằng nhau, bạn nộp sớm hơn sẽ được ưu tiên.

Mỗi lần đoán, các bạn hãy nộp chính xác ba chữ số vào bài này, chọn ngôn ngữ là TEXT. Cứ mỗi ~250~ điểm trong contest này, các bạn sẽ được nộp vào đây một lần, điều đó tương ứng với một cơ hội trúng giải. Nếu nộp quá số lần, các bạn sẽ bị loại khỏi giveaway. Chúng mình không thể xóa bài nộp của các bạn.

Ví dụ, bạn được ~1750~ điểm trong contest, bạn sẽ được nộp vào đây tối đa ~7~ lần.

Chúc các bạn may mắn.

Mô tả về cách chơi. Ở trong hình, bạn hãy gõ số may mắn mà bạn chọn (ở đây là ~203~), sau đó bấm Nộp bài.

Cho xâu ~s~ và xâu ~t~. Dữ liệu đảm bảo xâu ~t~ gồm các ký tự phân biệt.

Bạn được quyền đảo các ký tự trong xâu ~s~ theo bất kỳ thứ tự nào.

Hãy tìm cách đảo để ~t~ không nằm trong xâu ~s~ dưới dạng xâu con liên tiếp.

Nếu không tồn tại cách đảo nào, in ra ~-1~.

INPUT

Dòng đầu tiên là số nguyên dương ~t~ (~1 \le t \le 2000~) là số truy vấn.

~t~ dòng tiếp theo:

• Dòng thứ nhất gồm xâu ~s~ (~1 \le |s| \le 300~).
• Dòng thứ hai gồm xâu ~t~ (~1 \le |t| \le 4~).

OUTPUT

Với mỗi truy vấn, in ra xâu ~s~ đã được đảo để ~t~ không nằm trong xâu ~s~ dưới dạng xâu con liên tiếp.

Nếu không có cách đảo nào, in ra ~-1~.

SAMPLE INPUT

2
clueclue
clue
vnexpress
abc

SAMPLE OUTPUT

cluceelu
vnexpress

SUBTASKS

Cho dãy số ~a_1, a_2, ..., a_n~ và một số nguyên dương ~k~. Hỏi có tồn tại một cách chọn đúng ~k~ số trong dãy số ~a~ sao cho tổng các số đó chia hết cho 3 không?

INPUT

Dòng đầu tiên chứa số nguyên dương ~T~ là số test (~1 ≤ T ≤ 3 \times 10^5~). Sau đó là ~T~ bộ test như sau:

• Dòng đầu tiên mỗi test chứa hai số nguyên dương ~n,~ ~k~ (~1 \le k \le n ≤ 3 \times 10^5~).
• Dòng thứ hai mỗi test chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 10^9~)

Dữ liệu đầu vào đảm bảo rằng tổng ~n~ trong tất cả các test không vượt quá ~3 \times 10^5~

OUTPUT

In ra ~T~ dòng, mỗi dòng ghi YES nếu tồn tại cách chọn thỏa mãn, ngược lại ghi NO.

SAMPLE INPUT

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

SAMPLE OUTPUT

YES
YES

Giải thích: Ở test 1, có thể chọn các số 0 và 3 để tạo ra tổng bằng 3.

SUBTASKS

Cho dãy số ~a_1, a_2, ..., a_n~. Có ~q~ truy vấn, bao gồm ~2~ loại sau:

• Loại ~1~: ~1~ ~u~ ~v~, gán ~a_u = v~.
• Loại ~2~: ~2~ ~l~ ~r~, hãy in ra hai số ~i~ ~j~ bất kỳ sao cho ~l \le i \le j \le r~ và ~a_i \ne a_j~.

Nhiệm vụ của bạn hãy in ra các dòng là câu trả lời của từng truy vấn loại ~2~.

INPUT

• Dòng đầu tiên chứa hai số nguyên dương ~n,~ ~q~ (~1 \le n, q ≤ 3 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le |a_i| \le 10^9~).
• ~q~ dòng tiếp theo, mỗi dòng là một trong hai loại truy vấn:
  • ~1~ ~u~ ~v~ (~1 \le u \le n~, ~0 \le |v| \le 10^9~).
  • ~2~ ~l~ ~r~ (~1 \le l \le r \le n~).

OUTPUT

In ra nhiều dòng, mỗi dòng gồm hai số ~i~ và ~j~ là đáp số của từng truy vấn loại ~2~.

Nếu không có kết quả hợp lệ cho truy vấn loại ~2~, in ra ~-1 -1~.

SAMPLE INPUT

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

SAMPLE OUTPUT

3 4
-1 -1
2 4
-1 -1

SUBTASKS

Trong một thế giới hậu tận thế, Tổ chức Bảo vệ Dị điểm Toàn cầu (SCP) phát hiện ra một loại thông tin sống mới, gọi là Hệ thống Lượng tử Di truyền. Thông tin này được mã hóa thành các chuỗi ký tự và được lưu trữ trong một chuỗi ~s~.

Để kiểm soát dị điểm này, bạn phải đưa nó về trạng thái ổn định. Bạn có thể hoán đổi hai điểm dữ liệu ~s_i~ và ~s_j~ nếu thỏa mãn điều kiện: $$ | c_{pos(s_i)} - c_{pos(s_j)} | \le k. $$

~pos(s_i)~ là chỉ số của kí tự ~s_i~ trong bảng chữ cái (a là ~0~, b là ~1~, v.v.).

Bạn có thể hoán đổi bao nhiêu lần tùy ý.

Mục tiêu là đưa dị điểm ~s~ về trạng thái có thứ tự từ điển nhỏ nhất. Trạng thái này được coi là nền tảng nguyên thủy, vững chắc nhất cho mọi quá trình tổng hợp sau này và được gọi là ~\text{base}~ ~—~ Mẫu hình Thông tin Cơ sở.

Sau khi đã thiết lập thành công ~\text{base}~, Tổ chức cần kích hoạt một quá trình nhân rộng và mở rộng dữ liệu của dị điểm để nghiên cứu sâu hơn. Quá trình này diễn ra qua một số lượng xác định các "Chu kỳ".

Mỗi "Chu kỳ" tuân theo một quy tắc duy nhất, dựa trên một quy tắc nhất định được gọi là Bộ Tán xạ ~h~. Trong mỗi "Chu kỳ", mọi điểm dữ liệu trong chuỗi hiện tại sẽ được thay thế bằng một chuỗi các điểm dữ liệu mới.

Cụ thể, điểm dữ liệu tại vị trí ~i~ trong chuỗi sẽ được thay thế bởi ~h_{pos(s_i)}~ chữ cái liên tiếp tiếp theo trong bảng chữ cái. Nếu quá trình tán xạ vượt quá z, nó sẽ quay vòng lại từ a.

• Ví dụ: a với ~h_{pos(a)} = 3~ sẽ trở thành bcd.
• Ví dụ: y với ~h_{pos(y)} = 3~ sẽ trở thành zab.

Bạn cần tính toán tổng độ dài của chuỗi sau đúng ~m~ chu kỳ, chia dư cho ~10^9 + 7~.

INPUT

Dòng đầu tiên là ba số nguyên ~n, m, k~ ~(1 \le n \le 10^5, 1 \le k \le 10^9, 1 \le m \le 10^{18})~

Dòng thứ hai là xâu ~s~ chỉ bao gôm các kí tự thường

Dòng thứ ba là ~26~ số nguyên ~c_i~ ~(1 \le c_i \le 10^9)~

Dòng thứ tư là ~26~ số nguyên dương ~h_i~ ~(1 \le h_i \le 26)~

OUTPUT

Dòng đầu tiên in ra xâu ~\text{base}~

Dòng tiếp theo in ra tổng độ dài của chuỗi sau đúng ~m~ chu kỳ, chia dư cho ~10^9 + 7~.

SAMPLE INPUT

5 2 1
yycba
1 2 2 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 3 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

SAMPLE OUTPUT

abcyy
7

SUBTASKS

Giải thích

• Hoán đổi vị trí ~3~ với ~4~ ~(c \longleftrightarrow a)~. Vì ~|c_{pos(c)} - c_{pos(a)}| = |2 - 1| = 1 \le 1~.

Chuỗi ~\rightarrow~ y y a c b

• Hoán đổi vị trí ~1~ với ~4~ ~(y \longleftrightarrow c)~. Vì ~|c_{pos(y)} - c_{pos(c)}| = |3 - 2| = 1 \le 1~.

Chuỗi ~\rightarrow~ c y a y b

• Hoán đổi vị trí ~1~ với ~3~ ~(c \longleftrightarrow a)~. Vì ~|c_{pos(c)} - c_{pos(a)}| = |2 - 1| = 1 \le 1~.

Chuỗi ~\rightarrow~ a y c y b

• Hoán đổi vị trí ~2~ với ~5~ ~(y \longleftrightarrow b)~. Vì ~|c_{pos(y)} - c_{pos(b)}| = |3 - 2| = 1 \le 1~.

Chuỗi ~\rightarrow~ a b c y y

Sau các hoán đổi trên ta không thể thu được chuỗi nhỏ hơn theo thứ tự từ điển bằng bất kỳ hoán đổi hợp lệ nào khác.

Vậy ~\text{base}~ = abcyy.

Mở rộng theo ~m = 2~ chu kỳ (theo quy tắc Bộ Tán xạ ~h~) ~—~ chỉ tính độ dài:

Biến đổi lần ~1~ ~(m = 1)~:

• a biến thành b vì ~h_0 = 1~

• b biến thành c vì ~h_1 = 1~

• c biến thành d vì ~h_2 = 1~

• y biến thành z vì ~h_{24} = 1~

• y biến thành z vì ~h_{24}~ ~= 1~

~\rightarrow~ Chuỗi sau biến đổi thứ nhất: bcdzz

Biến đổi lần ~2 (m = 2)~:

• b biến thành c vì ~h_1 = 1~

• c biến thành d vì ~h_2 = 1~

• d biến thành e vì ~h_3 = 1~

• z biến thành ab vì ~h_{25} = 2~

• z biến thành ab vì ~h_{25} = 2~

~\rightarrow~ Chuỗi sau biến đổi thứ hai: cdeabab

Độ dài cuối cùng của chuỗi có ~7~ ký tự.

Có lẽ, trong số chúng ta, ai cũng từng nghe qua ít nhất một lần về đoạn hình nón khi nhập môn quy hoạch động.

Một dãy ~b_1, b_2, ..., b_m~ được định nghĩa là đoạn hình nón nếu như tồn tại giá trị ~k~ sao cho ~b_1 < b_2 < ... < b_k > b_{k+1} > b_{k+2} ... > b_m~. Lưu ý, ~k = 1~ hay ~k = m~ cũng được chấp nhận.

Cho dãy số ~a_1, a_2, ..., a_n~ và ~q~ truy vấn. Mỗi truy vấn bao gồm số nguyên dương ~x~ ~y~, mô tả cần gán ~a_x = y~. Nhiệm vụ của bạn là sau mỗi truy vấn, hãy tìm độ dài của đoạn hình nón liên tiếp dài nhất trong dãy ~a~.

Lưu ý, các truy vấn được giữ vĩnh viễn cho các truy vấn sau nó.

INPUT

Dòng đầu gồm hai số nguyên dương ~n~ và ~q~ (~2 \le n, q \le 2 \times 10^5~)

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^6~)

~q~ dòng tiếp theo, mỗi dòng thứ ~i~ chứa 2 số nguyên dương ~x~, ~y~ xác định thay đổi tại truy vấn thứ ~i~

Dữ liệu luôn đảm bảo ~2~ số cạnh nhau tại mọi thời điểm luôn khác nhau.

OUTPUT

~q~ dòng tiếp theo, dòng thứ ~i~ xác định số lượng đoạn hình nón dài nhất sau lần thay đổi tại truy vấn thứ ~i~

SAMPLE INPUT

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

SAMPLE OUTPUT

4
4

Trong truy vấn đầu tiên, dãy ~a~ là ~5, 2, 7, 6, 4, 5, 2, 3~. Dãy hình nón dài nhất là ~2, 7, 6, 4~.

Trong truy vấn thứ hai, dãy ~a~ là ~5, 2, 7, 6, 4, 5, 1, 3~. Dãy hình nón dài nhất là ~2, 7, 6, 4~.

SUBTASKS

Năm ~2030~, công ty TNHH Clue chính thức ra mắt, mở ra một hành trình đáng hy vọng ở phía trước. Bộ máy công ty như sau:

• Gồm ~n~ người, với duong3982 giữ chức Giám đốc - cũng là người nắm quyền cao nhất - được đánh số là ~1~.
• Với ~n-1~ người còn lại, mỗi người chỉ có duy nhất một người là cấp trên trực tiếp. Người ~x~ được gọi là cấp trên của ~y~ nếu tồn tại dãy ~x = u_0, u_1, ..., u_t = y~ sao cho ~u_{i-1}~ là cấp trên trực tiếp của ~y~ với ~i \in [1, t]~.

Từ khi công ty ra đời, nhiều vấn đề đã được mô hình hóa, khiến cho công ty vận hành trơn tru hơn trước. Để khích lệ, duong3982 đã rà soát lại và xác định được ~k~ người có đóng góp vào những thành công trên. Để cho các ban có thể sát sao hơn, duong3982 yêu cầu: Khi một người có thành tích, người đó và tất cả các cấp trên của người đó đều được thưởng do đã lập công.

Yêu cầu: Trong trường hợp tốt nhất, số người được duong3982 thưởng là bao nhiêu?

INPUT

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~1 \le k \le n \le 3 \times 10^5~).

Dòng thứ hai chứa ~n-1~ số nguyên dương ~p_2, p_3, ..., p_n~ (~1 \le p_i < i~) với ~p_i~ là cấp trên trực tiếp của người thứ ~i~.

OUTPUT

Một số nguyên dương duy nhất là đáp số đề bài.

SAMPLE INPUT

6 2
1 2 2 3 2

SAMPLE OUTPUT

5

Trong trường hợp tốt nhất, người ở vị trí ~5~ và ~6~ là người lập công, như vậy có ~5~ người được thưởng.

SUBTASKS

Tiến sĩ Nefario sở hữu một mã ~\text{ADN}~ được biểu thị dưới dạng một xâu ~S~ gồm các kí tự ~\text{latinh}~ in hoa (~A,B,C,\dots Z~) tương ứng với ~26~ loại nuclêôtít, Nefario sẽ thực hiện thao tác sau một số lần (có thể không thực hiện lần nào):

• Chọn một hoặc nhiều kí tự trong xâu ~S~ (tối đa ~25~ kí tự phân biệt, có thể chọn một kí tự nhiều lần), ghép các kí tự được chọn thành xâu mới ~T~.

• Xóa tất cả các kí tự vừa chọn khỏi ~S~.

• Thêm kí tự có thứ tự từ điển nhỏ nhất không tồn tại trong xâu ~T~ vào đầu xâu ~S~.

Tiến sĩ Nefario muốn biết số lượng xâu ~S~ phân biệt sau khi thực hiện các thao tác này trên ~S~, bạn hãy giúp Nefario trả lời câu hỏi này nhé.

Hai xâu ~S~ và ~T~ được gọi là phân biệt với nhau khi và chỉ khi số lần xuất hiện của một kí tự ~c~ bất kì trong hai xâu là khác nhau.

INPUT

Một dòng duy nhất gồm xâu ~S~ gồm các kí tự ~\text{latinh}~ in hoa (~|S|\le 100~).

OUTPUT

Một dòng duy nhất gồm số lượng xâu ~S~ phân biệt sau các thao tác bất kì. Kết quả được in ra sau khi ~\pmod{998244353}~.

SAMPLE INPUT 1

ABB

SAMPLE OUTPUT 1

12

SAMPLE INPUT 2

BC

SAMPLE OUTPUT 2

8

GIẢI THÍCH

Tại test mẫu thứ ~2~ ta có thể tạo được các xâu ~\text{BC},\text{AC},\text{B},\text{BA},\text{AA},\text{A},\text{C},\text{BB}~. Ví dụ trên xâu ban đầu ~\text{BC}~ ta chọn kí tự ~S_1~ và loại bỏ, thêm vào kí tự ~A~ (vì ~A~ là kí tự có thứ tự từ điển nhỏ nhất không tồn tại trong xâu ~T='B')~ được xâu ~\text{AC}~.

SUBTASKS