Ta định nghĩa một cây Trie như sau:

• Cây có gốc.

• Mỗi đỉnh ~i~ của cây thể hiện một xâu kí tự, ký hiệu là ~S_i~.

• Mỗi cạnh của Trie được gán một kí tự ~c~.

• Xâu ký tự ứng với đỉnh gốc là xâu rỗng.

• Với mỗi cạnh ~u, v~ được gán ký tự ~c~, trong đó u là đỉnh gần gốc hơn (u là cha của v), ~S_v = S_u + c~.

Cây Trie được gọi là hoàn hảo nếu như tất cả các giá trị ~S_i~ đôi một phân biệt.

Cho một cây ~T~ có ~n~ đỉnh, các cạnh được gán sẵn kí tự. Hãy đếm số đỉnh ~u~ sao cho ~T~ là một cây Trie hoàn hảo nếu chọn ~u~ làm gốc của ~T~.

Input

Vào từ file văn bản trie.inp:

Dòng đầu gồm một số nguyên dương ~n~ là số đỉnh trong cây ~(1 \le n \le 10^5)~.

~n - 1~ dòng tiếp theo, mỗi dòng có dạng ~u~ ~v~ ~c~ thể hiện một cạnh nối từ đỉnh ~u~ đến đỉnh ~v~ và được gán ký tự ~c~ ~(1\le u, v \le n, u \ne v, c~ là chữ cái tiếng Anh viết thường~)~.

Output

In ra file văn bản trie.out một số nguyên duy nhất là số đỉnh có thể chọn làm gốc để thu được một cây Trie hoàn hảo.

Scoring

Sample Input 1

10
7 5 w
6 7 w
8 7 b
1 8 v
3 7 f
2 8 a
4 6 y
9 3 m
10 5 q

Sample Output 1

4

Notes

Các đỉnh thỏa mãn là các đỉnh ~5, 6, 4, 10~.

Cho một dãy gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~.

Bạn được yêu cầu trả lời ~q~ truy vấn online:

• ~1~ ~l~ ~r~ ~type~: với ~type = 1~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ tăng dần. Ngược lại, với ~type = 2~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ giảm dần.

• ~2~ ~l~ ~r~: Tìm ~MEX(a_l, a_{l+1}, \dots, a_r)~.

Chú ý:

• ~MEX~ của một dãy số nguyên ~b~ gồm ~(b_1, b_2, ..., b_m)~ là số nguyên không âm nhỏ nhất không xuất hiện trong dãy đó.

• Ví dụ: ~MEX(0, 1, 2, 4, 5) = 3~, ~MEX(1, 1, 5, 100) = 0~.

Input

Vào từ file văn bản mexquery.inp:

Dòng đầu tiên gồm số nguyên dương ~n~ - độ dài của dãy ~a~ ~(1 \le n \le 3 \cdot 10^5)~.

Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 30)~.

Dòng thứ ba gồm số nguyên dương ~q~ - số truy vấn bạn cần trả lời ~(1 \le q \le 5 \cdot 10^4)~.

Trong ~q~ dòng cuối cùng, dòng thứ ~i~ ~(1 \le i \le q)~ có dạng như sau:

• ~1~ ~l~ ~r~ ~type~ ~(1 \le l, r \le n, 1 \le type \le 2)~: Với ~type = 1~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ tăng dần. Ngược lại, với ~type = 2~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ giảm dần.

• ~2~ ~l~ ~r~ ~(1 \le l, r \le n)~: Tìm ~MEX(a_l, a_{l+1}, \dots, a_r)~.

Output

In ra file văn bản mexquery.out:

• Gồm ~k~ dòng tương ứng ~k~ truy vấn loại ~2~, dòng thứ ~i~ gồm một số nguyên là kết quả của truy vấn thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

4
0
1

Giải đấu cờ vua siêu đại kiện tướng đang diễn ra tại Gibraltar. ~N~ đấu thủ sẽ thi đấu với nhau theo thể thức vòng tròn một lượt. Một trận thắng được ~1~ điểm, thua ~0~ điểm và hòa ~0.5~ điểm cho mỗi người. Kết thúc giải đấu, người có điểm số cao nhất sẽ nhận được chức vô địch và một triệu USD tiền thưởng. Nếu có nhiều kỳ thủ có số điểm bằng nhau, những kỳ thủ này sẽ thi đấu loạt tie-break để xác định theo thể thức cờ nhanh vì vậy kết quả ở loạt đấu vòng tròn một lượt không thể thể hiện được kết quả sẽ xảy ra ở loạt tie-break và ai cũng có thể là người đoạt chức vô địch. Giải đấu đã diễn ra được một số trận đấu và bạn hãy xác định xem những kì thủ nào vẫn còn cơ hội vô địch giải đấu.

Input

Vào từ file văn bản chess.inp:

• Dòng đầu chứa một số nguyên dương ~n~ ~(n \leq 30)~ là số kì thủ trong giải đấu.

• Mỗi dòng trong ~n~ dòng tiếp theo là một xâu ~s_i~, trong đó ký tự ~{s_i}_j~ cho biết kết quả của trận đấu của kì thủ thứ ~i~ với kì thủ thứ ~j~. (~{s_i}_j = 0/d/1~ lần lượt tương đương với việc kì thủ thứ ~i~ thua, hòa hoặc thắng kì thủ thứ ~j~)

• Dữ liệu đảm bảo kết quả của các trận đấu đã diễn ra là không mâu thuẫn.

Output

• In ra file văn bản chess.out số thứ tự của các kì thủ vẫn còn cơ hội vô địch giải đấu theo thứ tự tăng dần, các số cách nhau bởi một dấu cách.

Scoring

Sample Input 1

5
x.11d
.x1d1
00x.0
0d.x.
d01.x

Sample Output 1

1 2

Notes

Với bảng kết quả như trên, ta có điểm của ~5~ kỳ thủ lần lượt là: ~2.5, 2.5, 0, 0.5, 1.5~ và còn những trận sau chưa có kết quả: ~1-2, 3-4, 4-5~

Người ~1~ và ~2~ đều có khả năng vô địch nếu như thắng trong trận đấu cuối cùng của họ (trận ~1-2~) và sẽ có ~3.5~ điểm, ~3~ người còn lại không thể vượt được ~3.5~ điểm.

Trong trường hợp xâu là người thứ ~1~ và ~2~ hòa nhau, mỗi người sẽ có ~3~ điểm. Tuy nhiên, ~3~ người còn lại dù thắng hết cũng không thể đạt được tối thiểu là ~3~ điểm (Số điểm lớn nhất có thể có của ~3~ người lần lượt là: ~1, 2.5, 2.5)~. Do đó, ~3~ người còn lại không còn khả năng vô địch.