Cho một đồ thị gồm ~n~ đỉnh, ban đầu đồ thị không có cạnh nào. Trong đó, đỉnh thứ ~i~ có giá trị là ~i~.

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

• union ~u~ ~v~ (~1 \leq u, v \leq n~) — Nối một cạnh giữa hai đỉnh ~u~ và ~v~.

• get ~u~ (~1 \leq u \leq n~) — Trong thành phần chứa đỉnh ~u~, tìm giá trị đỉnh bé nhất, giá trị đỉnh lớn nhất và số lượng đỉnh của thành phần liên thông.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \leq n, m \leq 3 \times 10^5~) — Là số đỉnh của đồ thị và số truy vấn.

Trong ~m~ dòng tiếp theo, mỗi dòng là một loại truy vấn thuộc một trong hai loại trên.

Output

Với mỗi thao tác loại get, hãy in ra 3 số nguyên dương trên từng dòng. Thứ tự in của 3 số nguyên dương trên mỗi dòng lần lượt là: giá trị đỉnh bé nhất, giá trị đỉnh lớn nhất và số lượng đỉnh của thành phần liên thông.

Scoring

Sample Input 1

5 11
union 1 2
get 3
get 2
union 2 3
get 2
union 1 3
get 5
union 4 5
get 5
union 4 1
get 5

Sample Output 1

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

Cho một đồ thị vô hướng và một dãy các truy vấn thuộc một trong hai loại sau:

• cut ~u~ ~v~ — xóa cạnh ~u-v~ khỏi đồ thị;

• ask ~u~ ~v~ — kiểm tra xem hai đỉnh ~u~ và ~v~ có cùng thuộc một thành phần liên thông hay không.

Sau khi thực hiện tất cả truy vấn, đồ thị không còn cạnh nào. Tìm đáp án cho mỗi truy vấn thuộc loại ask.

Input

Dòng đầu tiên gồm ba số nguyên dương ~n, m~ và ~k~ (~1 \le n \le 50000, 0 \le m \le 100000, m \le k \le 150000~) — lần lượt là số lượng đỉnh, số lượng cạnh trong đồ thị và số lượng truy vấn cần thực hiện.

Mỗi dòng trong ~m~ dòng tiếp theo gồm hai số nguyên dương ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~) — hai đỉnh của cạnh thứ ~i~. Các đỉnh được đánh số từ ~1~, đồ thị không có khuyên và cạnh lặp.

Mỗi dòng trong ~k~ dòng tiếp theo mô tả một trong hai loại truy vấn sau:

• "cut ~u~ ~v~" — xóa cạnh giữa đỉnh ~u~ và ~v~

• "ask ~u~ ~v~" — kiểm tra xem hai đỉnh ~u~ và ~v~ có cùng thuộc một thành phần liên thông hay không

Mỗi cạnh trong đồ thị xuất hiện trong các truy vấn cut một lần.

Output

Với mỗi truy vấn thuộc loại ask, in ra "YES" nếu hai đỉnh đã cho cùng thuộc một thành phần liên thông, và "NO" trong trường hợp còn lại. Thứ tự in ra đáp án tương đương với thứ tự truy vấn ask xuất hiện.

Scoring

Sample Input 1

3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1

Sample Output 1

YES
YES
NO
NO

Cho một cây có ~n~ đỉnh. Ban đầu không có cạnh nào, mỗi đỉnh là gốc của chính đỉnh đó.

Bạn cần thực hiện hai loại truy vấn sau:

• Gốc ~a~ trở thành con của gốc ~b~ (và không còn là gốc nữa),

• Cho một node ~c~, in ra khoảng cách từ ~c~ đến gốc của nó.

Với truy vấn thứ hai, nếu ~c~ là gốc thì kết quả sẽ bằng 0, ngược lại kết quả sẽ là một số nguyên dương — độ "sâu" của node đó.

Viết chương trình giải quyết các truy vấn trên.

Input

Dòng đầu chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n, m \leq 3 \cdot 10^5)~ — số lượng đỉnh và số lượng truy vấn tương ứng.

~m~ dòng tiếp theo chứa các truy vấn. Truy vấn thứ nhất có dạng "~\texttt{1}~ ~a~ ~b~" ~(1 \leq a \neq b \leq n)~, trong đó ~a~ và ~b~ đều là các gốc. Truy vấn thứ hai có dạng "~\texttt{2}~ ~c~" ~(1 \leq c \leq n)~.

Output

Với mỗi truy vấn loại hai, in ra kết quả trên một dòng.

Scoring

Sample Input 1

10 20
1 9 4
1 2 6
2 10
1 10 5
2 5
1 7 4
1 8 5
2 1
1 6 5
1 3 5
1 1 4
1 5 4
2 7
2 2
2 4
2 3
2 4
2 2
2 2
2 10

Sample Output 1

0
0
0
1
3
0
2
0
3
3
2

BT mới mua được mảnh đất trên mặt trăng. Bản đồ của vùng đất là một lưới ô vuông ~n \times n~ được chia thành các ô vuông đơn vị. Các hàng đánh số ~1, 2, \ldots, n~ từ trên xuống dưới còn các cột đánh số ~1, 2, \ldots, n~ từ trái qua phải. Ô nằm ở giao hàng ~i~, cột ~j~ ký hiệu là ~(i,j)~ và có độ cao ~a_{ij}~. BT muốn mua một robot tự hành để đi lại trên vùng đất này. Robot loại ~D~ có khả năng di chuyển giữa hai ô nếu chênh lệch độ cao giữa chúng đúng bằng ~D~. Hãy giúp BT chọn một loại robot để có thể đắt xe vào một ô nào đó trên bảng sao cho từ ô đó có thể đi đến được nhiều ô khác nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~n\leq 1000~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên không âm, số thứ ~j~ là ~a_{ij}\leq 10^6~.

Output

• Một số nguyên duy nhất là số ô nhiều nhất mà robot có thể đến được (tính cả ô xuất phát) theo phương án chọn robot và ô xuất phát tối ưu.

Example

Input

5
0 3 6 3 0
3 7 0 7 3
0 0 9 0 6
3 7 0 7 9
0 3 6 3 6

Output

16

Quang đang sử dụng những con búp bê để dạy một số trẻ về các đồ vật có kích thước khác nhau. Những con búp bê này rỗng bên trong nên những con búp bê nhỏ hơn có thể được đặt bên trong những con búp bê lớn hơn.

Mỗi con búp bê có một kích thước nhất định. Một con búp bê có kích thước ~x~ có thể nằm gọn trong một con búp bê khác có kích thước ~y~ nếu ~y - x \geq 2~.

Một chồng búp bê được hình thành bằng cách chọn một số búp bê mà Quang có và liên tục lắp con búp bê nhỏ nhất vào con búp bê nhỏ thứ hai cho đến khi chỉ còn lại một con búp bê. Kích thước của chồng búp bê là số lượng búp bê được sử dụng để tạo ra nó.

Có ~n~ ngày. Vào ngày thứ ~i~ (~1 ≤ i ≤ n~), Quang sẽ mua một con búp bê có kích thước ~a_i~. Sau khi mua búp bê, anh ta sẽ cố gắng xây dựng một chồng búp bê với số lượng búp bê tối đa.

Yêu cầu: Hãy giúp Quang tính toán với mỗi ngày kích thước tối đa của chồng búp bê bằng cách sử dụng những con búp bê có sẵn trong ngày đó.

Input

• Dòng đầu chứa đúng một số nguyên ~n~ (~n ≤ 100000~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ cách nhau bởi dấu cách (~a_i \leq 5 \times 10^5~, ~\forall \ i : 1 ≤ i ≤ n~), đại diện cho kích thước của những con búp bê được mua vào mỗi ngày trong số ~n~ ngày.

Output

Ghi ra ~n~ số nguyên trên một dòng duy nhất cách nhau bởi dấu cách, số nguyên thứ ~i~ là kích thước tối đa của chồng búp bê sử dụng số búp bê có sẵn trong ngày đó.

Scoring

• Subtask 1 (25%): ~n ≤ 200~.
• Subtask 2 (25%): ~a_i~ không phải là bội số của ~2~ với mọi ~1 \leq i \leq n~.
• Subtask 3 (25%): ~a_i~ không phải là bội số của ~4~ với mọi ~1 \leq i \leq n~.
• Subtask 4 (25%): Không có ràng buộc gì thêm.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

1 1 2 2 3

Đại dịch Chow đã quay trở lại HNAMS.

Lần này, nó mang tới một biến thể virus mới với chu kì bệnh trong ~k~ ngày, sau khoảng thời gian đó, bệnh nhân được coi là đã không còn nhiễm dịch nữa. Do đây là một đại dịch nguy hiểm, chính phủ sẽ bảo đam an toàn bằng cách đánh dấu những người có thể nhiễm bệnh, đó là những người có liên hệ trực tiếp hoặc gián tiếp đối với người bệnh trong ~k~ ngày gần nhất (không phụ thuộc vào thứ tự liên hệ).

Chow là một căn bệnh rất lạ, bởi không ai có cơ chế miễn dịch với nó cả.

Bạn cần viết ra một chương trình để tính toán số người có khả năng nhiễm bệnh của một người được cho (nói cách khác là tính số người đã liên hệ với người được cho trong ~k~ ngày gần nhất).

Được biết, đất nước HNAMS có ~n~ người, và có ~q~ sự kiện như sau:

• ~1~ ~(x,y):~ người ~x~ và người ~y~ gặp nhau ~(x \neq y)~.
• ~2~ ~z:~ Hãy trả về số người có thể bị lây bệnh bởi ~z~ (tính cả ~z~).
• ~3~ ~:~ ngày hiện tại kết thúc, chuyển sang ngày mới.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,q,k~, lần lượt là số người, số sự kiện và số ngày trong chu kì bệnh ~(1 \le n \le 10^5; 1 \le q \le 5 \times 10^5; 1 \le k \le 10^5)~
• ~q~ dòng sau, mỗi dòng chứa một sự kiện ở một trong ~3~ dạng:
  • ~1~ ~(x,y):~ người ~x~ và người ~y~ gặp nhau ~(x \neq y)~.
  • ~2~ ~z:~ Hãy trả về số người có thể bị lây bệnh bởi ~z~ (tính cả ~z~).
  • ~3~ ~:~ ngày hiện tại kết thúc, chuyển sang ngày mới.

Output

• Với mỗi truy vấn dạng ~2~, in ra kết quả.

Subtask

• Sub ~1~ ~(50\%)~: ~1 \le n,q \le 1000~
• Sub ~2~ ~(50\%)~: Không có ràng buộc gì thêm.

Sample Input 1

10 27 2
1 3 9
2 9
1 1 3
1 3 1
2 4
1 3 8
1 6 5
3
1 9 2
1 8 3
2 9
1 3 1
2 5
1 4 6
3
3
2 4
3
1 9 10
1 7 1
3
2 2
3
1 5 6
1 1 4
3
2 6

Sample Output 1

2
1
5
2
1
1
2

Bạn được cho một cây gồm ~n~ đỉnh và ~m~ yêu cầu, mỗi yêu cầu là một đường đi trên cây từ ~u~ đến ~v~. Bạn phải tô mỗi cạnh trên cây bằng một màu từ ~1~ đến ~K~ sao cho với mỗi yêu cầu, đường đi của yêu cầu phải có ít nhất hai màu khác nhau.

Đếm số cách tô màu hợp lệ. Hai cách tô màu được coi là khác nhau nếu tồn tại một cạnh có màu khác nhau trong hai cách.

Input

• Dòng đầu chứa ba số nguyên dương ~n, m~ và ~k~ ~(1 ≤ n ≤ 70, 1 ≤ m ≤ 15, 1 ≤ k ≤ 10^9)~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 ≤ u, v ≤ n)~ mô tả một cạnh của cây.
• ~m~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(1 ≤ x, y ≤ n)~ mô tả một yêu cầu.

Output

• Một số nguyên là số cách tô màu hợp lệ — kết quả của bài toán lấy phần dư khi chia cho ~10^9 + 7~.

Scoring

• Subtask 1 (20% số điểm): ~m = 1~.
• Subtask 2 (20% số điểm): ~m = 2~.
• Subtask 3 (20% số điểm): Mỗi cạnh trên cây thuộc không quá ~1~ yêu cầu.
• Subtask 4 (20% số điểm): ~k = 2~.
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 1 3
1 2
2 3
1 3

Sample Output 1

6