Alice đang phải tạo dữ liệu là một đồ thị dạng cây. Cô đã tạo được một cây gồm ~n~ đỉnh, các đỉnh được đánh số hiệu từ ~1~ đến ~n~. Cạnh thứ ~k~ ~(1 \leq k \leq n - 1)~ nối hai đỉnh phân biệt có số hiệu ~u_k, v_k \ (1 \leq u_k, v_k \leq n)~. ALice muốn tạo ra các cây mới bằng cách xóa đi ít nhất một đỉnh và xóa tất cả các cạnh kề với đỉnh được xóa mà phần còn lại (có ít nhất một đỉnh) vẫn liên thông với nhau. Một cách xóa được gọi là đẹp nếu tập số hiệu của các đỉnh còn lại là một tập gồm các số hiệu liên tiếp nhau.

Yêu cầu:

Cho dãy ~(u_1, v_1), \ (u_2, v_2), \dots, \ (u_{n - 1}, v_{n - 1})~ mô tả cây, hãy đếm số cách xóa đẹp. Hai cách xóa được gọi là khác nhau nếu tồn tại một đỉnh trong cách này bị xóa mà cách kia không bị xóa.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n \ (1 \leq n \leq 3 \times 10^5)~.
• Dòng thứ ~k \ (1 \leq k \leq n - 1)~ chứa hai số nguyên dương ~u_k, v_k \ (1 \leq u_k, v_k \leq n)~.

Kết quả

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là số cách xóa đẹp.

Ràng buộc

• Subtask ~1 \ (10 \%)~: ~n \leq 100~ và đồ thị có dạng đường thẳng.
• Subtask ~2 \ (20 \%)~: ~n \leq 5000~ và đồ thị có dạng đường thẳng.
• Subtask ~3 \ (20 \%)~: Đồ thị có dạng đường thẳng.
• Subtask ~4 \ (20 \%)~: ~n \leq 100~.
• Subtask ~5 \ (10 \%)~: ~n \leq 5000~.
• Subtask ~6 \ (10 \%)~: Không có ràng buộc gì thêm.

Sample Input 1

4
1 2
3 2
4 2

Sample Output 1

8

Sample Input 2

5
1 5
5 3
3 4
4 2

Sample Output 2

9

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

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

Output:

5
9

Geto Suguru là một chú thuật sư đặc cấp và năng lực của anh là thu thập nguyền hồn. Mỗi con nguyền hồn đều có một mã định danh phân biệt, và đều có một chỉ số sức mạnh. Vào đầu mỗi ngày, có thể anh ấy sẽ thu phục một nguyền hồn hoặc có thể có một con nguyền hồn của anh chết đi. Từ những nguyền hồn anh ấy có, anh ấy có khả năng kết hợp nhiều nguyền hồn với nhau để tạo ra một nguyền hồn mạnh hơn. Khi những con nguyền hồn dung hợp lại, một con nguyền hồn mới có sức mạnh bằng tổng sức mạnh của chúng sẽ được tạo ra. Vào cuối ngày, Geto muốn biết được có bao nhiêu tổng sức mạnh khác nhau anh ấy có thể tạo ra bằng cách dung hợp các nguyền hồn con anh có (anh ấy có thể chọn một tập hợp các con nguyền hồn, tập hợp các con nguyền hồn được chọn để dung hợp có thể không có con nào hoặc chỉ có một con).

Mô tả đầu vào

• Dòng đầu chứa số nguyên dương ~q~ là số ngày
• ~q~, dòng sau mỗi dòng có dạng
  • Hai số nguyên ~x_i~ và ~a_i~ phân tách nhau bởi dấu cách: Geto thu phục được một con nguyền hồn có mã định danh ~x_i~ và sức mạnh của nó là ~a_i~
  • Tuy nhiên nếu ~a_i = -1~ nghĩa là con nguyền hồn có mã định danh ~x_i~ chết đi hay Geto không còn sở hữu nó nữa

Mô tả đầu ra

• ~q~ dòng mỗi dòng chứa một số duy nhất là số tổng sức mạnh anh ấy có thể dung hợp ra

Giới hạn:

• Trong mọi subtask: ~q \leq 5000~, ~-1 \leq a_i \leq 100~, ~1 \leq x_i \leq q~
• Subtask ~1~ chiếm ~20~% số điểm: ~q \leq 100~
• Subtask ~2~ chiếm ~30~% số điểm: ~q \leq 300~
• Subtask ~3~ chiếm ~50~% số điểm : Không ràng buộc gì thêm

Input mẫu

5
3 1
4 8
5 3
3 -1
1 7

Output mẫu

2
4
8
4
8

Giải thích:

• Ngày 1 có những con nguyền hồn có sức mạnh là: 1, có 2 tổng có thể tạo ra là 0 và 1
• Ngày 2 có những con nguyền hồn có sức mạnh là: 1, 8 có 4 tổng có thể tạo ra là 0, 1, 8, 9
• Ngày 3 có những con nguyền hồn có sức mạnh là: 1, 8, 3 có 8 tổng có thể tạo ra
• Ngày 4 có những con nguyền hồn có sức mạnh là: 8, 3 có 4 tổng có thể tạo ra
• Ngày 4 có những con nguyền hồn có sức mạnh là: 8, 3, 7 có 4 tổng có thể tạo ra

Satoshi có ~n~ con pokemon. Con thứ ~i~ có cấp độ ~a[i]~ ~(1 \leq a[i] \leq 10^9)~. Biết để có thể nâng cấp pokemon, Satoshi sẽ kết hợp ~2~ con pokemon có cùng cấp độ ~x~ để tạo một con mới cấp độ ~x + 1~.

Một dãy pokemon được gọi là đặc biệt nếu có thể kết hợp cả dãy để thành ~1~ con pokemon duy nhất. Ví dụ như dãy ~\{1, 2, 1\}~ có thể tạo thành một con pokemon cấp độ ~3~, dãy ~\{1, 2, 3, 1, 4, 5\}~ có thể tạo thành một con pokemon cấp độ ~6~, dãy ~\{1\}~ có thể tạo thành một con pokemon cấp độ ~1~.

Cho dãy ~a~, hãy đếm số dãy con liên tiếp là dãy đặc biệt.

Input

Dòng ~1~: Ghi số nguyên dương ~n~ ~(n≤10^5)~.

Dòng ~2~: Ghi ~n~ số nguyên của dãy ~a~.

Output

Dòng ~1~: Chứa kết quả của bài toán.

Scoring

Sample Input 1

5
1 2 3 1 2

Sample Output 1

6

Sample Explanation

• Có ~6~ dãy là ~\{1\}~, ~\{2\}~, ~\{3\}~, ~\{1\}~, ~\{2\}~, ~\{1, 2, 3, 1\}~.

Một cuộc đua robot trên mê cung được tổ chức tại XYZ. Mê cung có dạng hình chữ nhật và được chia thành ~n \times m~ ô được sắp xếp thành ~n~ hàng và ~m~ cột. Mỗi ô hoặc trống hoặc chứa chướng ngại vật.

Các thí sinh đăng ký robot của họ cho cuộc thi. Mỗi thí sinh sẽ nhận được tọa độ ngẫu nhiên của ô bắt đầu và ô đích. Sau đó, rô bốt được đặt vào ô bắt đầu và phải đến ô đích bằng một chuỗi các bước.

Để làm cho trò chơi trở nên khó khăn hơn, các quy tắc chỉ cho phép trong mỗi bước, robot chỉ có thể di chuyển sang một ô bên phải hoặc một ô bên dưới trong mê cung. Di chuyển robot theo bất kỳ hướng nào khác là không được phép.

Thí sinh có robot đi nhanh nhất từ ô bắt đầu đến ô đích sẽ chiến thắng cuộc thi. Nếu robot không đến ô đích trong thời hạn, thí sinh bị loại. Ban tổ chức cuộc thi nhận ra rằng nếu thí sinh có tọa độ xấu, robot sẽ không thể đến ô đích bằng bất kỳ chuỗi di chuyển nào. Trong trường hợp đó, họ muốn cung cấp cho thí sinh một cặp tọa độ khác.

Bạn được cung cấp một bản đồ của một mê cung có kích thước ~n \times m~ và ~q~ cặp tọa độ của ô bắt đầu và ô đích. Hãy xác định với từng cặp tọa độ xem có thể đi từ ô bắt đầu đến ô đích bằng cách sử dụng một chuỗi các bước sang phải hoặc đi xuống hay không.

Input

• Dòng ~1~: Ghi ~3~ số nguyên dương ~n, m, q~ ~(n, m≤1000, q \leq 10^6)~.
• ~n~ dòng tiếp theo mỗi dòng chứa ~m~ kí tự '.' hoặc '#' mô tả ô trống hoặc ô chứa vật cản.
• ~q~ dòng tiếp theo mỗi dòng chứa ~4~ số nguyên ~r_1,c_1,r_2,c_2~ mô tả ô bắt đầu ~(r_1,c_1)~ của robot và cần đi đến ô ~(r_2,c_2)~ ~(1≤r_1,r_2≤n,1≤c_1,c_2≤m)~.

Output

• Đưa ra ~q~ dòng là kết quả của mỗi truy vấn, đưa ra 'YES' nếu có thể di chuyển đến ô đích, ngược lại ghi ra 'NO'.

Scoring

Sample Input 1

3 4 5
.#..
.##.
....
1 1 3 4
1 3 3 4
1 1 1 1
1 1 2 4
2 1 2 4

Sample Output 1

YES
YES
YES
NO
NO

Cho ~G~ là một đồ thị vô hướng liên thông. Các đỉnh của ~G~ được đánh số từ ~1~ đến ~n~, các cạnh của ~G~ được đánh số từ ~1~ đến ~m~.

Với ~p~ ~=~ ~(p_1, p_2, ..., p_m)~ là một hoán vị của ~(1, 2, 3, . . . , m)~; ta định nghĩa trọng số của ~p~ là số ~i~ nhỏ nhất ~(0 ≤ i ≤ m)~ sao cho khi xóa hết các cạnh được đánh số ~p_i+1, p_i+2, . . . , p_m~ thì ~G~ vẫn liên thông.

Ban đầu ~p~ ~=~ ~(1, 2, 3, . . . , m)~. Cho ~Q~ thao tác có dạng ~(i, j)~ là đổi giá trị ~p_i~ với ~p_j~ . Các thao tác được thực hiện tuần tự theo thứ tự thời gian và thực sự làm thay đổi hoán vị ~p~. Sau mỗi thao tác, hãy tính toán và đưa ra trọng số của ~p~.

Lưu ý là ta sẽ không thực sự xóa cạnh nào khỏi đồ thị; tức là đồ thị vẫn được giữ nguyên sau các thao tác.

Input

• Dòng ~1~: Ghi ~3~ số nguyên dương ~n, m, q~ ~(1 \leq n, m, q \leq 10^5)~.
• ~m~ dòng tiếp theo mỗi dòng chứa hai số nguyên mô tả một cạnh : ~u, v~.
• ~q~ dòng tiếp theo mỗi dòng chứa hai số nguyên mô tả một thao tác: ~i, j~.

Output

• Đưa ra ~q~ dòng là kết quả của mỗi truy vấn.

Scoring

Sample Input 1

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

Sample Output 1

4
3
3