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]~.