Cho một đồ thị gồm ~n~ đỉnh, đỉnh thứ ~i~ có giá trị là ~a_i~. Đồ thị gồm ~\frac{N \cdot (N-1)}{2}~ cạnh, cạnh nối hai đỉnh ~i~ và ~j~ có trọng số là XOR của hai số ~a_i~ và ~a_j~. Bạn hãy tìm cây khung nhỏ nhất của đồ thị đã cho.

Input

Dòng đầu tiên gồm một số nguyên ~n~ (~1 \le n \le 10^5~) là số đỉnh của đồ thị.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i < 2^{30}~).

Output

In một số nguyên duy nhất là cây khung nhỏ nhất của đồ thị.

Scoring

Subtask ~1~ (~20\%~):

• ~n \le 10^5~

• ~a_i < 2^{10}~

Subtask ~2~ (~20\%~):

• ~n \le 2500~

• ~a_i < 2^{20}~

Subtask ~3~ (~60\%~): Không có ràng buộc gì thêm.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

8

Nghe nói crush sắp chuyển trường, vì không còn nhiều thời gian nên bé Lộkk quyết định viết thư tình gửi cho nàng. Nhưng khổ nỗi, chữ bé Lộkk rất xấu, xấu đến mức chính cậu còn không đọc được thì sao crush có thể hiểu được tấm chân tình của cậu chứ. Nhưng may thay, ở nhà cậu lại có sẵn một cái máy in từ thời ~MU~ vô địch ~EPL~, tuy cổ nhưng vẫn có thể dùng được.

Ban đầu trên màn hình máy in không có kí tự nào, chiếc máy in cho phép thực hiện các thao tác sau:

• Thêm một kí tự vào cuối từ hiện tại trên màn hình.

• Xóa kí tự cuối cùng của từ hiện tại trên màn hình (chỉ được xóa nếu trên màn hình có ít nhất một kí tự).

• In ra từ hiện tại trên màn hình.

Lộkk có ~N~ từ cần gửi tượng trưng cho ~N~ trái tim mà cậu dành cho crush. Vì mỗi từ có một ý nghĩa riêng nên Lộkk có thể in ra ~N~ từ theo thứ tự bất kì, nhưng Lộkk phải in chính xác từng từ (tức là mỗi từ phải in vào đúng một lần riêng biệt và không được có thêm các kí tự khác trong từ đó).

Nhưng vì máy in này rất cổ nên loại mực in và loại pin của nó cũng rất đắt ~!!??~, mà Lộkk lỡ đặt hết vào ~Messi~ nên giờ cậu không còn quá nhiều tiền. Lộkk muốn nhờ bạn giúp tìm cách in sao cho tốn ít thao tác nhất (cũng như ít tiền nhất).

Input

• Dòng đầu tiên chứa số nguyên dương ~N~, số từ mà Lộkk cần in (~1 \leq N \leq 10^5~).

• ~N~ dòng tiếp theo, mỗi dòng chứa một từ chỉ bao gồm các chữ cái tiếng Anh in thường ('a' - 'z') và có độ dài trong khoảng từ ~1~ đến ~20~.

Output

• Dòng đầu tiên chứa số nguyên ~M~, là số thao tác tối thiểu để in ra các từ.

• Dòng thứ hai chứa ~M~ kí tự viết liền thể hiện chuỗi các thao tác theo thứ tự đó. Mỗi thao tác được biểu diễn bằng các kí tự như sau:

  • Thêm một kí tự được biểu diễn bằng chính kí tự đó.

  • Xóa một kí tự được biểu diễn bằng kí tự '-' (dấu trừ, mã ASCII là 45).

  • In ra từ hiện tại được biểu diễn bằng kí tự 'P' (chữ P viết hoa).

Nếu có nhiều cách in thỏa mãn, bạn được phép in ra một cách bất kì.

Sample Input 1

3
xycj
xycr
xycrg

Sample Output 1

10
xycjP-rPgP

Giải bóng đá trường X có ~N~ đội bóng đăng ký đánh số từ ~1~ đến ~N~. Tên của đội bóng thứ ~i~ là xâu ký tự ~s_i~ gồm các ký tự tiếng Anh in thường, và không có hai đội bóng nào trùng tên. Để tiết kiệm mực in danh sách, trường X quyết định bỏ một số ký tự (có thể là không ký tự nào) khỏi cuối tên của mỗi đội, sao cho sau khi bỏ tên:

• Không đội bóng nào có xâu tên rỗng.

• Không có hai đội bóng nào trùng tên.

• Tổng độ dài các xâu tên của các đội bóng là nhỏ nhất có thể.

Hãy giúp trường X thực hiện việc này nhé!

Input

Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~. ~N~ dòng tiếp theo, dòng thứ ~i~ gồm xâu ký tự ~s_i~ gồm các ký tự tiếng Anh in thường. Dữ liệu đảm bảo tổng độ dài tên các đội bóng không vượt quá ~10^5~.

Output

In ra một số nguyên dương duy nhất là tổng độ dài tên các đội bóng sau khi bỏ.

Sample Input 1

4
baba
ab
a
b

Sample Output 1

6

Sample Input 2

6
a
abbb
aab
ba
aa
baaa

Sample Output 2

11

Notes

Giải thích ví dụ

• Ví dụ 1: Đổi ~baba~ thành ~ba~.

• Ví dụ 2: Đổi ~abbb~ thành ~ab~, ~ba~ thành ~b~ và ~baaa~ thành ~ba~.

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

[placeholder] đang muốn trở thành 1 tỉ phú.

Đến thời điểm hiện tại, [placeholder] đã hoàn thành được giai đoạn 1 của công cuộc trở thành tỉ phú: bỏ học.

Không bỏ phí một giây nào, [placeholder] lập tức quyết định bắt đầu giai đoạn 2: tạo ra tìm kiếm động cơ G****e. Mỗi giây, tìm kiếm động cơ G****e của [placeholder] phải xử lý được các truy vấn sau:

- POST x c: Thêm 1 xâu được tạo bằng cách lấy xâu tại giây thứ ~x~ và nối vào đó chữ cái ~c~

- DELETE x: Xâu được tạo ra vào giây thứ ~x~ được xóa bỏ. Nếu xâu tại thời điểm ~x~ đã bị xóa từ trước thì G****e không làm gì cả.

- GET s k: Cho xâu ~s~, tìm xâu có thứ tự từ điển thứ ~k~ nhận ~s~ làm tiền tố

Đang chuẩn bị code thì [placeholder] bỗng nhớ ra 1 bài học từ môn Tư duy Sigma nam tại Đại học Chen lấn của hàng đầu G nổi tiếng Ăn riêu Tết: một Sigma nam không bao giờ tự làm công việc tay chân. Vì vậy, [placeholder] đã quyết định thuê bạn code, rồi dùng thời gian quý báu của bản thân để retweet nhà thầu khoán đại tài Melon Husk.

Input

Dòng đầu tiên chứa số ~n~ (~n \le 250000~), số giây tìm kiếm động cơ G****e phải chạy. ~n~ dòng tiếp theo, mỗi dòng là một truy vấn.

Các truy vấn POST và DELETE đảm bảo tại giây thứ ~x~ cũng là một truy vấn POST. Quy ước xâu tạo ra vào giây ~0~ là xâu rỗng. Input đảm bảo trong mọi thời điểm các xâu chưa bị xóa đều phân biệt.

Tổng độ dài các xâu ~s~ không vượt quá ~10^6~.

Output

Với mỗi truy vấn GET, in ra trên ~1~ dòng thời điểm đáp án xâu đó được tạo ra. Trong trường hợp không tồn tại ít nhất ~k~ xâu hợp lệ, in ra "404".

Sample Input 1

13
POST 0 l
POST 1 m
POST 2 a
POST 3 o
POST 1 o
POST 5 l
POST 3 i
POST 3 u
GET lmao 1
GET lmao 2
GET lma 2
DELETE 7
GET lma 2

Sample Output 1

4
404
7
4

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

Chào mọi người. God QM vừa mới viết specification cho ngôn ngữ lập trình TRIETORTURE, nhưng vì bận đánh cp nên chưa impl compiler được. HTK rảnh lắm nhưng không muốn impl compiler vì lười. Mọi người hãy giúp god QM và HTK impl compiler nhé.

TRIETORTURE là một ngôn ngữ lập trình rất orz. Đọc specification của QM là biết orz rồi. Nó có 2 tính năng: khai báo xâu và cộng xâu.

Dòng đầu tiên của chương trình là một số nguyên ~n~—số lượng câu lệnh. Câu lệnh thứ ~i~ tạo ra xâu có chỉ số là ~i~.

Cú pháp khai báo xâu là DECLARE s, với s là 1 xâu có độ dài từ 1 đến 10^6 và chỉ bao gồm các kí tự từ a đến z. Ví dụ, để khai báo xâu có nội dung là abc, ta ghi DECLARE abc.

Cú pháp cộng xâu là CONCATENATE i j, với i và j là chỉ số của 2 xâu. Lưu ý rằng i và j có thể trùng nhau.

Sau khi các câu lệnh của chương trình được thực hiện, các xâu có thể trở nên rất lớn. Vì vậy, việc in đầy đủ một xâu bất kì là bất khả thi. Chình vì vậy, lập trình viên cần phải cho ~m~ xâu và ~i~—chỉ số của một xâu cụ thể, và ngôn ngữ TRIETORTURE sẽ thông báo nếu ít nhất 1 trong ~m~ xâu là tiền tố của xâu thứ ~i~.

God QM muốn dự án hoàn thành sớm. Nếu có người impl được compiler, god QM sẽ hack server VNOJ để cho người đó đai đỏ! Chúc mọi người giành được phần quà của god QM nhé.

Input

Dòng đầu tiên gồm một số nguyên dương ~t \leq 10^6~—số lượng test. Sau đây là mô tả từng test.

Dòng đầu tiên của mỗi bộ test gồm một số nguyên dương ~n \leq 10^6~. ~n~ dòng tiếp theo là các câu lệnh của chương trình.

Dòng thứ ~n + 1~ gồm hai số nguyên dương ~m~ và ~i~. ~m~ là số xâu và ~i~ là chỉ số của xâu trong chương trình. ~m~ dòng tiếp theo là các xâu cần kiểm tra, chỉ bao gồm các kí tự từ a đến z.

Tổng ~n~ trong tất cả các test không vượt quá ~10^6~.

Tổng ~m~ trong tất cả các test không vượt quá ~10^6~.

Tổng độ dài các xâu trong các câu lệnh DECLARE trong tất cả các test không vượt quá 10^6.

Tổng độ dài ~m~ xâu cần kiểm tra trong tất cả các test không vượt quá ~10^6~.

Output

Với mỗi test, in ra YES nếu ít nhất 1 trong m xâu là tiền tố của xâu thứ i, ngược lại in NO.

Sample Input 1

1
3
DECLARE a
CONCATENATE 1 1
CONCATENATE 1 1
2 3
aaa
bbb

Sample Output 1

NO

Dạo gần đây, Phúc mới dần được học cách sử dụng các câu lệnh terminal để quản lý máy tính một cách hiệu quả hơn. Hào hứng trước những kiến thức mới, Phúc rất mong muốn được mau chóng áp dụng chúng vào thực tiễn, trước mắt là trong việc dọn dẹp các tập tin lộn xộn trên máy tính của mình.

Phúc muốn xóa ~n~ file trên máy tính của mình, tuy nhiên vì số lượng file quá lớn nên việc dọn dẹp thủ công đối với Phúc dường như là không thể vì Phúc lười. May mắn thay, trong các câu lệnh terminal Phúc vừa học có câu lệnh rm [tiền tố]* có thể giúp Phúc xóa đồng loạt tất cả các file có tên nhận *[tiền tố] làm tiền tố của nó.*

Tuy nhiên, để đảm bảo an ninh dữ liệu trên máy tính (tránh việc người dùng xóa quá nhiều file dẫn đến mất thông tin), các nhà sản xuất khi cài đặt đã giới hạn mỗi lần máy tính sử dụng câu lệnh trên chỉ được xóa tối đa ~k~ file cùng lúc. Chính vì thế, Phúc cần phải tính toán hợp lý mình cần gõ những câu lệnh nào để vừa có thể dọn dẹp một cách hiệu quả vừa không phải tốn sức gõ quá nhiều lệnh.

Các bạn hãy giúp Phúc tính xem Phúc cần gõ ít nhất bao nhiêu lần dòng lệnh rm trên để dọn dẹp máy tính của mình nhé!

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n~, ~k~ ~(1 \le n, k \le 3 \cdot 10^5)~ - số lượng file trong máy tính của Phúc cần xóa và số lượng file tối đa một lần máy của Phúc có thể xóa được.

~n~ dòng tiếp theo, mỗi dòng gồm ~1~ xâu ~s~ ~(1 \le |s| \le 3 \cdot 10^5)~ là tên của các file trong máy tính của Phúc cần được dọn dẹp.

Biết rằng tên của tất cả các file trong máy tính của Phúc đều chỉ gồm các chữ cái in thường a-z, đôi một khác nhau, và tổng độ dài tên của tất cả các file không vượt quá ~3 \cdot 10^5~.

Output

Gồm ~1~ số nguyên dương duy nhất là số lần tối thiểu Phúc cần thực hiện lệnh để dọn dẹp hết toàn bộ file cần xóa trong máy.

Scoring

• ~10\%~ số test có ~k=1~.

• ~30\%~ số test có ~\sum |s| \le 5000~.

• ~60\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

4 2
a
abc
abd
b

Sample Output 1

2

Sample Input 2

4 2
d
c
ab
a

Sample Output 2

2

Sample Input 3

5 3
please
remove
all
these
files

Sample Output 3

3