Bạn được cho một xâu ~S~ có độ dài ~n~ gồm các chữ cái từ a đến z. Nhiệm vụ của bạn là đếm số xâu con liên tiếp mà mỗi cặp kí tự đặc biệt trong xâu con đó có khoảng cách không nhỏ hơn ~k~ (~k \le n~).

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~ và ~k~ ~(1 \le k \le n \le 10^5; 1 \le m \le 10)~ lần lượt là độ dài của xâu ~S~, số lượng kí tự đặc biệt và khoảng cách yêu cầu giữa hai kí tự đặc biệt bất kì.
• Dòng thứ hai chứa xâu ~S~ gồm các chữ cái từ a đến z.
• Dòng cuối cùng gồm ~m~ kí tự là các kí tự đặc biệt, dữ liệu đảm bảo ~k~ kí tự này phân biệt

Output

• Gồm một dòng duy nhất là số lượng xâu con liên tiếp thỏa mãn đề bài

Substask

• ~30\%~ số test: ~1 \le k \le n \le 10^3~.
• ~20\%~ số test: ~1 \le k \le n \le 10^5~, trong xâu chỉ có đúng ~2~ vị trí có kí tự đặc biệt.
• ~50\%~ số test: ~1 \le k \le n \le 10^5~.

Sample Input 1

6 2 2
acbabc
a b

Sample Output 1

10

Explanation 1

Các xâu con thỏa mãn là: a, c, b, a, b, c, ac, acb, cb, bc.

Cho số nguyên không âm ~n~, cần tìm số ~m~ nhỏ nhất thỏa mãn điều kiện:

• Số ~m~ lớn hơn hoặc bằng ~n~;
• Tổng các chữ số của ~m~ nhỏ hơn tổng các chữ số của ~n~;

Dữ liệu: Vào từ thiết bị vào chuẩn có dạng:

• Dòng đầu chứa số nguyên dương ~t~ là số bộ dữ liệu;
• Dòng thứ ~i~ (~1 \le i \le t~) chứa một số nguyên không âm ~n~.

Kết quả: Ghi ra thiết bị ra chuẩn gồm ~t~ dòng, mỗi dòng là số ~m~ tương ứng tìm được, nếu không tồn tại số đưa ra ~-1~.

Ví dụ:

Subtask 1 (60 điểm): ~n \le 10^6; t \le 3~;
Subtask 2 (20 điểm): ~n \le 10^6; t \le 3 \times 10^4~;
Subtask 3 (20 điểm): ~n \le 10^{16}; t \le 3 \times 10^4~;

Alice có một bảng kích thước ~m \times n~, các hàng được đánh số từ ~1~ đến ~m~ theo chiều từ trên xuống, các hàng được đánh số từ ~1~ đến ~n~ theo chiều từ trái sang phải. Ô nằm giao giữa hàng ~i~ (~1 \le i \le m~) và cột ~j~ (~1 \le j \le n~) gọi là ô ~(i, j)~. Ban đầu, toàn bộ bảng là màu trắng (màu ~0~), Alice thực hiện ~k~ thao tác tô màu như sau:

• Chọn một hình chữ nhật nằm trong bảng chiếm nguyên các ô và một màu ~c~ (~1 \le c \le 100~);
• Tô đè tất cả các ô trong hình chữ nhật vừa chọn thành màu ~c~.

Yêu cầu: Cho ~m, n~ là kích thước bảng và dãy gồm ~k~ thao tác tô màu, hãy xác định bảng màu mà Alice nhận được.

Input:

• Dòng đầu tiên gồm ba số nguyên ~m, n, k~ (~m, n, k \le 100~);
• Dòng thứ ~s~ (~1 \le s \le k~) chứa năm số nguyên ~x_s, y_s, u_s, v_s, c_s~, trong đó ~(x_s, y_s)~ và ~(u_s, v_s)~ tương ứng là ô góc trái trên và ô góc phải dưới của hình chữ nhật được chọn ở thao tác tô màu thứ ~s~, ~c_s~ là màu sẽ tô cho hình chữ nhật đó.

Output

• Dòng thứ ~i~ (~1 \le i \le m~) trong dòng sau chứa ~n~ số nguyên ~a_{i1}, a_{i2}, ..., a_{in}~ mô tả màu trên hàng ~i~ của bảng màu Alice.

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12

Cho ~n + 1~ hình chữ nhật trên mặt phẳng ~Oxy~, các hình chữ nhật đều có các cạnh song song hoặc vuông góc với trục toạ độ. Hãy tìm điểm ~(x, y)~ nằm trong ít nhất ~n~ hình chữ nhật đã cho. Điểm ~(x, y)~ được gọi là nằm trong hình chữ nhật xác định bởi hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ nếu:

• ~min(x_1, x_2) \le x \le max(x_1, x_2)~;
• ~min(y_1, y_2) \le y \le max(y_1, y_2)~.

Dữ liệu: Vào từ thiết bị vào chuẩn có dạng:

• Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~);
• ~n + 1~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~x_1, y_1, x_2, y_2~ (~0 \le x_1, y_1, x_2, y_2 \le 10^9~) mô tả hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ là hai góc của hình chữ nhật, dữ liệu đảm bảo hai điểm này là phân biệt.

Kết quả: Ghi ra thiết bị ra chuẩn hai số nguyên ~x, y~ là toạ độ của điểm nằm trong ít nhất ~n~ hình chữ nhật, nếu có nhiều điểm thoả mãn thì đưa ra điểm có ~x~ nhỏ nhất, nếu có nhiều điểm thoả mãn có cùng ~x~ nhỏ nhất thì đưa ra điểm có ~y~ nhỏ nhất. Nếu không có điểm nào thỏa mãn chỉ ghi ~-1~.

Ví dụ:

Subtask 1 (25 điểm): ~x_1, x_2, y_1, y_2 \le 20~;
Subtask 2 (25 điểm): ~x_1, x_2, y_1, y_2 \le 1000~;
Subtask 3 (25 điểm): ~n \le 2000~;
Subtask 4 (25 điểm): Không có ràng buộc gì thêm.

An và Bình đang có một số nguyên dương ~X~ và muốn tách nó thành tổng hai số nguyên dương ~A~ và ~B~. Giá trị thực sự của một số nguyên dương không nằm ở độ lớn mà được quyết định bởi tổng chữ số. Hai bạn sẽ cảm thấy vui nếu ~A~ và ~B~ có tổng chữ số bằng nhau.

Yêu cầu: Có ~T~ giả định, mỗi giả định cung cấp số nguyên dương ~X~. Với mỗi giả định, hãy giúp An và Bình tìm hai số nguyên dương ~A~ và ~B~ có tổng bằng ~X~ và tổng chữ số của hai số bằng nhau.

Input:

• Dòng đầu tiên chứa một số nguyên ~T~ (~1 \le T \le 10000~);
• Mỗi dòng trong ~T~ dòng tiếp theo chứa một số nguyên dương ~X~ (~X \ge 2~).

Output:

• Với mỗi giả định, in ra hai số nguyên ~A~ và ~B~ bất kì thoả mãn đề bài trên một dòng. Nếu không tồn tại đáp án, in ra ~-1~.

Gọi ~C(X)~ và ~S(X)~ là số chữ số và tổng chữ số của số nguyên dương ~X~.
Subtask 1 (20 điểm): ~X \le 10000~ với mọi giả định.
Subtask 2 (30 điểm): Tổng ~C(X)~ của các giả định không vượt quá ~1000~.
Subtask 3 (20 điểm): Tổng ~C(X)~ của các giả định không quá ~10^6~ và ~S(X)~ chẵn với mọi giả định.
Subtask 4 (30 điểm): Tổng ~C(X)~ của các giả định không vượt quá ~10^6~.

Cho một đồ thị vô hướng có ~n~ đỉnh, đỉnh thứ ~i~ có màu ~a_i~. Ban đầu đồ thị chưa có cạnh nào.

Cho ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

• ~1~ ~u~ ~v~: Thêm một cạnh nối ~u~ và ~v~.
• ~2~ ~u~ ~c~: Tính số đỉnh có màu ~c~ trong vùng liên thông của ~u~.

Input:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n \le 10^5, q \le 2*10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~. ~(a_i \le n)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm ba số nguyên dương, số nguyên đầu tiên là loại của truy vấn (~1~ hoặc ~2~), hai số nguyên dương còn lại không vượt quá ~n~.

Output

• Với mỗi truy vấn loại ~2~, in ra trên một dòng kết quả của truy vấn đó.

Subtask

• Có ~30\%~ số test chứa ~n,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
0
3
1

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le n)~

Output

• In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~1000000007~

Subtask :

• Subtask ~1~: ~n \le 20~ ~(20\%)~
• Subtask ~2~: ~n \le 200~ ~(20\%)~
• Subtask ~3~: ~n \le 2000~ và ~a_i \le 200~ ~(25\%)~
• Subtask ~4~: ~n \le 2000~ ~(35\%)~

Sample Input 1:

4
3 3 4 2

Sample Output 1:

9