Cho một danh sách gồm ~N~ xâu. Hãy in ra thứ tự của các xâu sau khi được sắp xếp.

Input

• Dòng đầu gồm số nguyên dương ~N~ (~1 \le N \le 10^6~).
• ~N~ dòng tiếp theo, mỗi dòng gồm một xâu kí tự chứa các kí tự từ a đến z.
• Dữ liệu đảm bảo tổng độ dài các xâu không quá ~10^6~.

Output

• Gồm một dòng duy nhất, là thứ tự ban đầu của xâu thứ ~i~ khi danh sách được sắp xếp tăng dần theo thứ tự từ điển. Nếu hai xâu có giá trị bằng nhau, ưu tiên xếp xâu có thứ tự ban đầu ở trước.

Sample Input

3
ab
b
abc

Sample Output

1
3
2

Bạn có một máy in và cần in ~n~ từ để ghép thành một khẩu hiệu. Máy in có một khay để xếp các miếng kim loại (mỗi miếng chứa một kí tự) để tạo thành từ. Ban đầu khay rỗng, mỗi lượt bạn được thao tác một trong ba loại sau:

• Xếp thêm một miếng kim loại chứa một kí tự vào cuối khay;
• Loại bỏ một miếng kim loại chứa một kí tự ở cuối khay;
• In ra từ được tạo bởi các kí tự trên khay.

Vào cuối quá trình in, bạn được phép để lại các miếng kim loại trên khay, ngoài ra bạn được phép in các từ theo bất kì thứ tự nào.

Yêu cầu: Cho ~n~ từ, hãy tính số thao tác ít nhất để in được ~n~ từ đó.

Input

• Dòng đầu chứa số nguyên dương ~n~ ;
• Tiếp theo là ~n~ dòng, mỗi dòng chứa một từ cần in, các từ chỉ gồm các kí tự a đến z và tổng số các kí tự không vượt quá ~1000000~

Output

• Gồm một dòng, chứa số thao tác ít nhất cần thực hiện để in n từ trên

Constraints

• Subtask 1 : ~n \le 20~.
• Subtask 2: Không có ràng buộc gì thêm.

Example

Sample Input

3
print
the 
poem

Sample Output

20

Cho tập ~S~ ban đầu rỗng. Bạn được cho ~Q~ truy vấn, mỗi truy vấn thuộc một trong các loại sau:

• ~I~ ~x~: Nếu ~x~ không thuộc ~S~, thêm ~x~ vào ~S~.
• ~D~ ~x~: Nếu ~x~ thuộc ~S~, xóa ~x~ khỏi ~S~.
• ~K~ ~k~: Tìm phần tử lớn thứ ~k~ của ~S~.
• ~C~ ~x~: In ra số lượng số thuộc ~S~ bé hơn ~x~.

Input

• Dòng đầu gồm số nguyên dương ~Q~ (~1 \le Q \le 2 \cdot 10^5~).
• ~Q~ dòng sau, mỗi dòng là một trong các loại truy vấn trên. Dữ liệu đảm bảo ~-10^9 \le x, k \le 10^9~.

Output

• Với mỗi truy vấn ~K~ và ~C~, in ra câu trả lời. Với truy vấn ~K~, nếu ~k~ lớn hơn số phần tử của ~S~, in ra invalid.

Example

Sample Input

8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2

Sample Output

1
2
2
invalid

Cho tập ~S~ ban đầu rỗng. Bạn được cho ~Q~ truy vấn, mỗi truy vấn thuộc một trong các loại sau:

• ~0~ ~x~: Nếu ~x~ không thuộc ~S~, thêm ~x~ vào ~S~.
• ~1~ ~x~: Nếu ~x~ thuộc ~S~, xóa ~x~ khỏi ~S~.
• ~2~ ~x~: Tìm ~\min_{i \in S} i \oplus x~ trong đó ~\oplus~ là phép toán xor.

Input

• Dòng đầu gồm số nguyên dương ~Q~ (~1 \le Q \le 5 \cdot 10^5~).
• ~Q~ dòng sau, mỗi dòng là một trong các loại truy vấn trên. Dữ liệu đảm bảo ~1 \le x < 2^{30}~.

Output

• Với mỗi truy vấn loại ~2~, in ra câu trả lời.

Example

Sample Input

6
0 6
0 7
2 5
1 7
1 10
2 7

Sample Output

2
1

Cho một dãy số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~. Đếm số cách chia dãy này thành ~k~ đoạn con liên tiếp, thỏa mãn tổng ~XOR~ đoạn thứ ~i~ ~(i \le k)~ nằm trong đoạn ~[L_i, R_i]~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^5, n * k \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~ ~(a_i \le 10^9)~.
• ~k~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~L_i~ và ~R_i~ là điều kiện của đoạn thứ ~i~ ~1 \le L_i \le R_i \le 10^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán. Do kết quả có thể khá lớn, hãy in kết quả ~MOD~ ~10^9 + 7~.

Sample Input 1

4 2
1 2 3 4
1 4
2 10

Sample Output 1

2

Cho một tập ~S~ ban đầu rỗng, bạn cần thực hiện ~q~ truy vấn có dạng như sau:

• ~1~ ~x~: Thêm số nguyên ~x~ vào tập ~S~. ~(0 \le x \le 10^9)~

• ~2~ ~x~: Xóa số nguyên ~x~ ra khỏi tập ~S~, nếu số ~x~ xuất hiện nhiều lần, ta chỉ xóa nó một lần, nếu số đó không xuất hiện trong tập ~S~, ta bỏ qua truy vấn này.

• ~3~ ~L~ ~R~: In ra tổng các phần tử trong tập ~S~ có giá trị trong đoạn ~[L,R]~. ~(0 \le L \le R \le 10^9)~

• ~4~ ~k~: In ra phần tử bé thứ ~k~ trong tập ~S~. ~(1 \le K \le |S|)~

• ~5~ ~a~: In ra ~max (a \oplus x) \, \forall \, x \in S~, ở đây ~\oplus~ là phép ~xor~.

Input

Dòng đầu tiên gồm số nguyên ~q~ ~(1 \le q \le 2*10^5)~ mô tả số truy vấn.

~q~ dòng sau, mỗi dòng miêu tả một truy vấn.

Output

Mỗi dòng in ra kết quả theo thứ tự nhập vào của các truy vấn loại ~3,4,5~.

Sample Input 1

10
1 3
1 4
3 1 3
4 2
1 2
2 2
4 1
2 5
3 1 6
5 8

Sample Output 1

3
4
3
7
12

Bờm viết một chương trình hỗ trợ học ngoại ngữ. Module quản lí từ vựng với phép tìm kiếm từ được Bờm xây dựng theo quy trình: giả sử danh sách từ chương trình đang có là ~w_1, w_2, . . . , w_N~ , mỗi khi nhận được mẫu tìm ~P~, chương trình sẽ lần lượt so sánh ~P~ với ~w_1, w_2, . . .~ cho đến khi gặp từ trùng với ~P~ hoặc đã hết danh sách từ. Khi so sánh ~P~ với các từ, chương trình sẽ lần lượt so sánh các kí tự từ trái qua phải cho đến khi gặp kí tự sai khác hay một trong hai từ kết thúc (khi đó nếu cả hai từ cùng kết thúc là tìm kiếm thành công).

Để khảo sát hiệu năng của module tìm kiếm, Bờm xây dựng một danh sách N từ và thực hiện tìm kiếm ~Q~ mẫu, với mỗi mẫu Bờm cần xác định số thao tác cơ sở mà chương trình thực hiện, thao tác cơ sở là một lần so sánh kí tự hoặc một lần xử lí khi gặp kết thúc từ. Số thao tác cơ sở thực hiện với mỗi mẫu tìm kiếm sẽ bằng tổng của: số lượng từ được so sánh với mẫu, độ dài của tiền tố chung dài nhất của mỗi từ với mẫu.

Hãy giúp Bờm thực hiện việc khảo sát trên mà không cần thực hiện chương trình của Bờm.

Input

• Dòng ~1~ gồm hai số nguyên ~N,Q~ ~(1 \le N,Q \le 3\times10^4)~
• ~N~ dòng sau, dòng thứ ~i~ ghi từ ~w_i~.
• ~Q~ dòng sau, mỗi dòng là một từ mẫu tì kiếm.

Tất cả các từ trong input đều có độ dài không quá ~30~ và chỉ chứa các chữ cái latin in thường.

Output

• Gồm ~Q~ dòng: dòng ~i~ ghi số nguyên là số thao tác cơ sở mà chương trình của Bờm sẽ thực hiện khi tìm kiếm từ mẫu thứ ~i~.

Sample Input 1

4 2
c
cvp
cvy
cvn
cv
cvy

Sample Output 1

11
9

Một lớp học nọ có ~n~ học sinh, tên của học sinh thứ ~i~ được biểu diễn bằng một string ~s_i~.

Có ~n~ biệt danh cũng được biểu diễn bằng các string ~p_i~.

Ta kí hiệu ~lcp(a,b)~ là độ dài tiền tố chung dài nhất giữa hai xâu ~a~ và ~b~.

Bạn có thể chọn ~c~ là dãy hoán vị từ ~1~ tới ~n~, tương đương với việc gán cho bạn thứ ~i~ biệt danh là ~p_{c_i}~. Cách chọn này có độ "hoàn hảo" là ~\sum lcp(s_i,p_{c_i}) \forall i \in[1,n]~.

Hãy tìm dãy hoán vị ~c~ có độ hoàn hảo lớn nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ là xâu ~s_i~ miêu tả tên của bạn thứ ~i~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ là xâu ~p_i~ miêu tả biệt danh thứ ~i~.
• Lưu ý rằng có thể có các tên hoặc biệt danh trùng với nhau.

Constraints

• ~1 \le n \le 10^5~
• Tổng kí tự của tất cả các xâu không quá ~10^6~.

Output

• In ra độ hoàn hảo lớn nhất tìm được.

Sample Input 1

3
chau
huy
hoang
homhinh
hoanhi
chumchim

Sample Output 1

7

Explanation 1

• chau sẽ ghép với chumchim và có ~lcp~ là ~2~.
• huy sẽ ghép với homhinh và có ~lcp~ là ~1~.
• hoang sẽ ghép với hoanhi và có ~lcp~ là ~4~.

Cho mảng ~A_0~ có độ dài ~n~, bạn cần thực hiện ~q~ truy vấn, mỗi truy vấn thứ ~i~ thuộc trong ~2~ loại sau :

• ~1~ ~id~ ~v:~ Copy mảng ~A_{id}~ vào ~A_i~, sau đó thêm ~v~ vào cuối mảng ~A_i~.

• ~2~ ~id~ ~v:~ Copy mảng ~A_{id}~ vào ~A_i~, sau đó thực hiện ~XOR~ tất cả các phần tử của mảng ~A_i~ cho ~v~.

Sau khi thực hiện ~q~ truy vấn, hãy cho biết phần từ nhỏ nhất trong từng mảng ~A_0, A_1, \ldots ,A_q~.

Input

• Dòng đầu tiên nhập ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 10^5)~.

• Dòng thứ hai nhập ~n~ số nguyên của dãy ~A_0~ ~(1 \le A_{0_i} \le 2^{30})~.

• ~q~ dòng tiếp theo, dòng thứ ~i~ nhập ~3~ số ~type_i, id_i, v_i~ ~(1 \le type_i \le 2, 0 \le id_i < i, 0 \le v_i \le 2^{30})~.

Output

• In ra ~q + 1~ số nguyên không âm trên một dòng, số thứ ~i~ cho biết phần tử nhỏ nhất của mảng ~A_i~.

Scoring

Sample Input 1

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

Sample Output 1

2 2 1 1 2

Notes

• ~A_0 = \{2, 3 \}~.

• ~A_1 = \{2, 3, 4 \}~.

• ~A_2 = \{7, 6, 1 \}~.

• ~A_3 = \{7, 6, 1, 6\}~.

• ~A_4 = \{2, 3, 7\}~.

Alice là một kỹ sư đang làm việc trên một loại vi xử lý mới. Bộ vi xử lý làm việc trên tập số nguyên không âm ~S~ (các số có thể xuất hiện nhiều lần) để mô phỏng sự sống trong Matrix. Ban đầu tập ~S~ là rỗng, bộ vi xử lý có các loại truy vấn sau:

• Truy vấn dạng 0 x: thêm số nguyên ~x~ vào ~S~ ~(0 \le x \le 10^5)~. Nếu ~x~ đã có trong ~S~ thì vẫn thêm bình thường.
• Truy vấn dạng 1 x: xóa một lần xuất hiện của ~x~ khỏi ~S~ ~(0 \le x \le 10^5)~. Nếu ~x~ không có trong ~S~ thì không làm gì.
• Truy vấn dạng 2 a: thay đổi toàn bộ tập ~S~ bằng phép XOR với ~a~ ~(0 \le a \le 10^5)~. Tức là mỗi phần tử ~x~ trong ~S~ được thay bằng ~x \oplus a~.
• Truy vấn dạng 3 k: tính tổng ~k~ phần tử nhỏ nhất trong ~S~ ~(0 \le k \le |S|)~.

Input

• Dòng đầu tiên chứa số nguyên dương ~Q~ — số lượng truy vấn ~(1 \le Q \le 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên mô tả truy vấn.

Output

• Với mỗi truy vấn loại 3 k, in ra một dòng là tổng ~k~ phần tử nhỏ nhất hiện tại trong ~S~.

Constraints

• 25% số điểm: ~Q \le 1000~.
• 25% số điểm: ~Q \le 10^5~ và không có truy vấn loại 2.
• 25% số điểm: ~Q \le 10^5~ và ~k \le 10~.
• 25% số điểm: ~Q \le 10^5~.

Example

Input

6
0 1
2 2
0 3
3 2
2 2
3 1

Ouput

6
1

https://oj.hncode.edu.vn/problem/dictionarythtb

nop o day nhe

Người ngoài hành tinh quyết định tới thăm các em học sinh của HNAms. Tuy nhiên vì ngôn ngữ bất đồng nên các em không hiểu những người ngoài hành tinh muốn nói gì. Vì vậy các em phải mang theo từ điển của mình ra để cho họ xem. Sau đó các em sẽ đoán xem là họ muốn nói đến từ nào trong từ điển. Từ điển cũng chỉ gồm ~26~ chữ cái thường từ ~a~ đến ~z~. Tuy nhiên vì không thể giải thích được với nhau nên hiện tại bước đầu giao tiếp vẫn là đoán từ và các câu hỏi để đoán từ phải vô cùng đơn giản. Người ngoài hành tinh chỉ có thể hiểu các câu hỏi sau:

1. Có bao nhiêu kí tự ~C~ trong từ đó?
2. Kí tự tại vị trí ~X~ là kí tự gì?

Nhiệm vụ của các bạn là viết một chương trình, sử dụng các câu lệnh được cung cấp để thực hiện khảo sát từ điển trong một bộ dữ liệu vào và đưa ra từ mà người ngoài hành tinh muốn nói là từ gì.

Input

• Dòng đầu tiên là số nguyên dương ~N~ (~1 \le N \le 10^6~) là số từ trong từ điển.
• ~N~ dòng tiếp theo mô tả từ điển chỉ gồm danh sách các từ đôi một khác nhau, trong đó mỗi từ nằm trên một dòng và chỉ gồm các chữ cái in thường từ ~a~ đến ~z~ dài tối đa ~50~ kí tự.

Interaction

Để tương tác với máy chấm, hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và em đọc vào. Lưu ý flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

Các lệnh được sử dụng:

• count c (~c~ là một kí tự bất kì từ a đến z): máy sẽ in ra số lượng kí tự c trong từ cần tìm. Chi phí sử dụng hàm count c 1 lần là 1 đơn vị.
• getpos x (~x~ là một số nguyên dương): máy sẽ in ra kí tự tại vị trí x trong từ cần tìm (từ trái sang phải, xâu được đánh số từ 1). Nếu ~x~ lớn hơn độ dài của từ, máy sẽ in ra kí tự #. Chi phí sử dụng hàm getpos x 1 lần là 10 đơn vị.
• answer s (~s~ là một xâu kí tự): là từ mà em đã xác định được. Chi phí sử dụng thủ tục answer() là 0 đơn vị. Chương trình bắt buộc phải gọi thủ tục answer() một lần duy nhất, nếu không sẽ bị 0 điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Scoring

• Với mỗi test, nếu chương trình của bạn gọi thủ tục answer() với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá 1000 đơn vị hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó. Số điểm cho mỗi test sẽ giảm dần khi chi phí bạn sử dụng tăng lên.

Sample Input 1

7
cat
can
mic
man
tiger
hello
world

Sample Output 1

Giả sử từ người ngoài hành tinh muốn nói là cat. Các hoạt động nhập xuất có thể diễn ra như sau:

>> getpos 4
<< #
>> count c
<< 1
>> count a
<< 1
>> count n
<< 0
>> answer cat

Explaination

• Độ dài của từ cat là ~3~ nên khi hỏi độ dài bằng ~4~ vượt quá độ dài ~3~, máy in ra dấu #
• Trong từ cat có 1 kí tự c nên máy in ra ~1~
• Trong từ cat có 1 kí tự a nên máy in ra ~1~
• Trong từ cat không có kí tự n nên máy in ra ~0~
• Như vậy bạn đã trả lời đúng với chi phí sử dụng là ~13~. Chương trình khi in ra answer cat sẽ đưa đáp án đồng thời thoát chương trình chạy của bạn.