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ữ liệu vào từ file văn bản copyarray.inp

• 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

Kết quả in ra file văn bản copyarray.out

• 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\}~.

Khu đô thị SuperVilla có qui hoạch giống như một hình chữ nhật gồm ~m \times n~ ô đất, ô đất thứ ~i~ từ phía Bắc và ~j~ từ phía Tây gọi là ô ~(i,j)~. Trên mỗi ô đất, nhà đầu tư sẽ quyết định xây một ngôi biệt thự hoặc một công trình công cộng mang tầm cỡ quốc gia.

Vì là khu đô thị cao cấp nên các con đường sẽ nối từ ô đất này sang ô đất khác, đồng thời các con đường sẽ chỉ có một chiều. Cụ thể, từ một ô đất ~(x,y)~ có một con đường dẫn tới ô đất ~(x+1,y)~ và ~(x,y+1)~ nếu hai ô này tồn tại; mặt khác các công trình công cộng là bị cấm đi vào (nhằm tránh thiệt hại không đáng có cho công trình quốc gia)

Quân và Hiển là đôi bạn thân, nhưng do vì bị o rờ dét nhiều quá nên Hiển cảm thấy Quân rất phiền và lăn ra dỗi; không vừa, Quân dùng chiến thuật "gậy ông đập lưng ông" cũng quay ra dỗi ngược; thế là mình mất nhau hai người dỗi nhau. Trước đó Quân và Hiển đã hẹn cùng nhau mua nhà tại khu SuperVilla, tiền đã cọc nên không thể bùng kèo. Và họ quyết định mua hai ngôi biệt thự sao cho từ nơi ở của Quân không thể đến được nơi ở của Hiển và từ nơi ở của Hiển cũng không thể đến được nơi ở của Quân

Yêu cầu: Quân và Hiển không thèm nói chuyện với nhau nên không thống nhất được phương án. Bạn hãy giúp Quân và Hiển đếm số cách mua biệt như vậy nhé. Hai cách mua gọi là khác nhau nếu vị trí của hai căn biệt thự là khác nhau trong hai cách (Xem test ví dụ).

Input

Dữ liệu vào từ file văn bản villa.inp

• Dòng đầu chứa hai số nguyên dương ~m,n~ (~1 \le m,n \le 2000~).

• ~m~ dòng tiếp, dòng thứ ~i~ chứa ~n~ kí tự ~a_{i,1},a_{i,2},…,a_{i,n}~ thuộc một trong hai loại {.,#} mô tả khu SuperVilla; nếu ~a_{i,j}=~ '.' thì trên ô ~(i,j)~ xây một ngôi biệt thự, ngược lại thì trên đó là một công trình công cộng cấp quốc gia.

• Dữ liệu đảm bảo tất cả các biệt thự đều có đường đi tới từ ô đất ~(1,1)~ và có đường đi tới ô đất ~(m,n)~ mà không đi qua các công trình công cộng mang tầm cỡ quốc gia.

Output

Kết quả in ra file văn bản villa.out

• In ra một số nguyên duy nhất là số cách mua nhà của Quân và Hiển mà bạn tìm được.

Scoring

Sample Input 1

3 3
..#
..#
#..

Sample Output 1

1

Giải thích

Chỉ có một cách mua là chọn hai căn biệt thự ~(1, 2)~ và ~(2, 1)~.

Cho một xâu ~s~, ta gọi một phép nén xâu ~s~ là việc thực hiện các thao tác sau:

• Tìm xâu ~t~ thỏa mãn có thể tạo ra ~s~ bằng cách lặp lại ~t~ một số lần

• Tìm số ~c~ thỏa mãn để tạo ra xâu ~s~ cần viết liên tiếp ~c~ lần xâu ~t~

• Khi đó, xâu ~p=c+t~ là xâu nén của ~s~

Ví dụ: ~p(~"ababab"~)=~"3ab", ~p(~"aaaaaaaaaaaa"~)=~"6aa" hoặc "12a", ~p(~"abc"~)=~"1abc".

Với ~|s|~ là kích thước của xâu ~s~

Yêu cầu: Hãy chia xâu ~s~ thành các xâu con liên tiếp ~s_1,s_2,...,s_k~ và nén chúng sao cho tổng độ dài các xâu sau khi nén các xâu là bé nhất

Input

Dữ liệu vào từ file văn bản compstr.inp

Một dòng duy nhất chứa xâu kí tự ~s~ (~|s|\le 5000~). Dữ liệu đảm bảo xâu ~s~ chỉ gồm các chữ cái tiếng Anh in thường.

Output

Kết quả in ra file văn bản compstr.out

In ra một số nguyên duy nhất là tổng độ dài các xâu nén trong phương án tìm được.

Scoring

Sample Input 1

ababbbbaba

Sample Output 1

8

Sample Input 2

ttuxtuxtxtaba

Sample Output 2

12

Notes

Ở ví dụ thứ nhất, xâu ~s~ được chia thành ~3~ xâu con liên tiếp: "abab", "bb" và "baba"

• ~p~("abab") = "2ab"

• ~p~("bb") = "2b"

• ~p~("baba") = "2ba"

Tổng độ dài các xâu con sau khi nén bằng ~8~.