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

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

Cho một đồ thị vô hướng có ~n~ đỉnh, đỉnh thứ ~i~ có màu ~a_i~. Ban đầu đồ thị chưa có cạnh nào.

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

• ~1~ ~u~ ~v~: Thêm một cạnh nối ~u~ và ~v~.
• ~2~ ~u~ ~c~: Tính số đỉnh có màu ~c~ trong vùng liên thông của ~u~.

Input:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n \le 10^5, q \le 2*10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~. ~(a_i \le n)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm ba số nguyên dương, số nguyên đầu tiên là loại của truy vấn (~1~ hoặc ~2~), hai số nguyên dương còn lại không vượt quá ~n~.

Output

• Với mỗi truy vấn loại ~2~, in ra trên một dòng kết quả của truy vấn đó.

Subtask

• Có ~30\%~ số test chứa ~n,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
0
3
1

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

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có ~n~ bến xe buýt được đánh số từ ~1~ tới ~n~ và có ~m~ tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải ~A~ hoặc ~B~. Cụ thể, tuyến thứ ~i~ ~(1 \le i \le m)~ di chuyển giữa hai bến ui và vi với giá vé do công ty quản lý quy định là ~w_i~.

Lưu ý là giữa hai bến có thể có nhiều hơn một tuyến xe buýt. Hai công ty ~A~ và ~B~ đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty ~A~ sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty ~A~ mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty ~B~ cũng có chính sách tương tự: khách hàng sẽ chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến thuộc công ty ~B~ mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt ~s~ và nơi làm của Alice ở gần bến xe buýt ~t~ nên hàng ngày Alice đều phải đi lại giữa hai bến này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~.

Input:

• Dòng đầu tiên chứa bốn số nguyên dương ~n, m, s~ và ~t~ ~(n, m \le 50000; s, t \le n; s \neq t)~;
• Dòng thứ ~i (1 \le i \le m)~ trong ~m~ dòng tiếp theo chứa bốn số nguyên dương ~c_i, u_i, v_i, w_i~ ~(u_i, v_i \le n; u_i \neq v_i; w_i \le 10^9)~ mô tả tuyến xe buýt thứ i trong đó ~c_i = 1~ nếu tuyến này được điều hành bởi công ty ~A~ hoặc ~c_i = 2~ nếu tuyến này được điều hành bởi công ty ~B~.

Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt ~s~ và ~t~ thông qua ~m~ tuyến xe.

Output:

• In ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~ cho Alice.

Subtask

• Subtask ~1~ ~(30\%)~: tất cả xe buýt đều được điều hành bởi công ty ~A~.
• Subtask ~2~ ~(30\%)~: ~n,m \le 5000~
• Subtask ~3~ ~(40\%)~: không ràng buộc gì thêm.

Sample Input 1

6 7 1 4
1 1 2 4
2 2 3 7
1 3 4 6
2 1 6 5
1 6 5 5
2 5 4 8
2 2 5 2

Sample Output 1

12

Explanation 1

Để đi từ ~1~ tới ~4~, Alice đi tuyến ~(1,2)~ của công ty ~A~ và hai tuyến ~(2,5)~ và ~(5,4)~ của công ty ~B~. Khi đó Alice cần trả cho công ty ~A~ ~4~ và công ty ~B~ ~8~ đơn vị tiền.

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

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Các cạnh được đánh số từ ~1~ tới ~m~, cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~.

Bạn cần xử lí ~q~ truy vấn, truy vấn thứ ~i~ có dạng sau:

• Cho hai số ~L_i~ và ~R_i~, giả sử chúng ta xóa hết các cạnh được đánh số trong khoảng ~[L_i,R_i]~, hỏi rằng liệu đồ thị mới có tồn tại ít nhất một chu trình lẻ hay không.
• Lưu ý rằng đây chỉ là giả định, các truy vấn ta chỉ xét với đồ thị gốc.

Input

• Dòng đầu gồm ba số nguyên ~n,m,q~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~u_i,v_i~ miêu tả cạnh thứ ~i~.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~L_i~, ~R_i~ miêu tả truy vấn thứ ~i~.

Output

• Với mỗi truy vấn, in ra "0" nếu như không tồn tại chu trình lẻ, ngược lại in ra "1".

Constraints

• ~1 \le n,m,q \le 2 \times 10^5~.
• ~1 \le u_i \neq v_i \le n~.
• ~1 \le L_i \le R_i \le n~

Subtask

• ~20\%~ số điểm có ~n,m,q \le 2000~.
• ~30\%~ số điểm có ~L_i = 1 \forall i \in [1,q]~.
• ~30\%~ số điểm có ~Q \le 2000~
• ~20\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

7 9 4
1 3
1 4
2 5
3 6
4 6
1 6
3 2
5 7
2 7

1 2
3 5
4 7
8 9

Sample Output 1

1
0
1
1