Quân có đồ thị vô hướng, liên thông ~n~ đỉnh, ~m~ cạnh. Quân cần xử lý ~q~ truy vấn có dạng sau:

• ~A\ B\ C\ D~: Thêm cạnh ~A - B~, cho biết, đồ thị mới có bao nhiêu cạnh là cầu nằm trên bất kỳ đường đi đơn nào đi từ ~C \rightarrow D~.

Biết rằng, các truy vấn độc lập với nhau (Tức là cạnh được thêm vào chỉ tồn tại cho đến hết truy vấn đó).

Nhắc lại: Một cạnh được gọi là cầu nếu xóa cạnh đó thì số miền liên thông tăng lên.

Input

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

• Dòng đầu gồm ba số nguyên dương ~n, m, q~ lần lượt là số đỉnh, số cạnh của đồ thị và số truy vấn cần xử lý (~1 \le n, m, q \le 10^5~).

• ~m~ dòng tiếp theo, mỗi dòng gồm hai số ~u, v~ biểu diễn cạnh ~u - v~ trên đồ thị (~1 \le u, v \le n~).

• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số ~A, B, C, D~, biểu diễn một truy vấn có dạng ~A\ B\ C\ D~ (~1 \le A, B, C, D \le n~).

Output

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

In ra ~q~ dòng tương ứng với câu trả lời cho ~q~ truy vấn.

Scoring

Sample Input 1

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

Sample Output 1

1
0

Notes

Trong cả ~2~ truy vấn, ta chỉ thêm cạnh ~4 - 6~. Sau khi thêm cạnh ~4 - 6~, đồ thị sẽ như trên.

Trong truy vấn ~1~, các đường đi từ ~4 \rightarrow 5~ bao gồm:

• ~4 \rightarrow 6 \rightarrow 3 \rightarrow 5~

• ~4 \rightarrow 1 \rightarrow 3 \rightarrow 5~

• ~4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 5~

Ta thấy cạnh ~3 - 5~ là cầu, và nằm trên đường đi từ ~4 \rightarrow 5~. Vì chỉ có cạnh ~3 - 5~ là cầu, đáp án là ~1~.

Trong truy vấn ~2~, không có cầu nào nằm trên đường đi từ ~1 \rightarrow 2~. Vì vậy, đáp án là ~0~.

Với hai dãy số ~x~, ~y~; người ta định nghĩa ~x~ là dãy con của ~y~ nếu có thể thu được ~x~ bằng cách xóa đi một số phần tử của ~y~ (Có thể không xóa hoặc xóa tất cả) và giữ nguyên thứ tự các phần tử còn lại. Ví dụ:

• ~[1,3,5]~ là dãy con của ~[1,2,3,4,5]~

• ~[2,4]~ là dãy con của ~[1,2,3,4,5]~

• ~[2,1,3]~ không là dãy con của ~[1,2,3,4,5]~

Cho hai dãy ~a~, ~b~ có kích thước lần lượt là ~m~, ~n~. Định dãy con chung dài nhất của hai dãy ~a~ và ~b~ là dãy ~c~ dài nhất vừa là dãy con của ~a~, vừa là dãy con của ~b~; có thể tồn tại nhiều hơn một dãy như vậy. Hai dãy con chung dài nhất ~x~ và ~y~ gọi là khác nhau nếu tồn tại một vị trí ~i~ mà tại đó ~x_i \neq y_i~.

Yêu cầu: Bạn hãy tính độ dài và đếm số dãy con chung dài nhất của ~a~ và ~b~ nhé. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~123456789~.

Input

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

- Dòng đầu chứa hai số nguyên dương ~m~, ~n~ (~1 \leq n, m \leq 10^4~) là kích thước hai dãy ~a~, ~b~.

- Dòng thứ hai chứa ~m~ số nguyên dương ~a_1, a_2, \cdots , a_m~ (~1 \leq a_i ≤ 10^9~) mô tả dãy ~a~.

- Dòng thứ ba chứa ~n~ số nguyên dương ~b_1, b_2, \cdots , b_n~ (~1 \leq b_i \leq 10^9~) mô tả dãy số ~b~.

Output

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

- Hai số nguyên lần lượt là độ dài dãy con chung dài nhất của ~a~, ~b~ và số lượng dãy như vậy.

Scoring

Sample Input 1

2 2
1 1
2 2

Sample Output 1

0 1

Sample Input 2

3 3
1 2 2
2 1 1

Sample Output 2

1 2

Sample Input 3

4 4
4 3 2 1
2 3 4 1

Sample Output 3

2 3

Notes

Ở test thứ nhất: Có 1 dãy thỏa mãn là dãy rỗng.

Ở test thứ hai: Có 2 dãy thỏa mãn là ~[1], [2]~.

Ở test thứ nhất: Có 3 dãy thỏa mãn là ~[2, 1], [3, 1]~ và ~[4, 1]~.

Bất phương trình tuyến tính là bất phương trình có dạng như sau: $$a_1 \times x_1 + a_2 \times x_2 + \ldots + a_n \times x_n \leq m$$ Trong đó ~a_1~, ~a_2~, ~\ldots~, ~a_n~ lần lượt được gọi là hệ số của ~x_1~, ~x_2~, ~\ldots~, ~x_n~; còn ~m~ được gọi là hệ số tự do.

Một nghiệm của bất phương trình là một bộ giá trị (~x_1~, ~x_2~, ~\ldots~, ~x_n~) = (~b_1~, ~b_2~, ~\ldots~, ~b_n~) mà khi thay vào thỏa mãn bất phương trình trên.

Yêu cầu: Cho ~n~ và các hệ số ~a_1~, ~a_2~, ~\ldots~, ~a_n~, ~m~; hãy đếm số nghiệm nguyên dương của bất phương trình ấy.

Input

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

• Dòng đầu tiên chứa hai số nguyên dương ~n~, ~m~ (~n \leq 10~, ~m \leq 10^9~).

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, ~\ldots~, ~a_n~ (~a_i \leq 10~).

Output

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

• In ra một số nguyên duy nhất là số nghiệm nguyên dương của phương trình, vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.

Scoring

Sample Input 1

5 15
1 2 3 4 5

Sample Output 1

1

Sample Input 2

5 45
1 2 3 2 1

Sample Output 2

79660