Dãy con của một dãy cho trước thu được bằng cách giữ nguyên thứ tự và xóa một số phần từ của dãy đó. Cho hai dãy số nguyên ~a_1~, ~a_2~,…,~a_n~ và ~b_1~, ~b_2~,…,~b_m~. Dãy ~c_1~, ~c_2~,…,~c_k~ được gọi là đẹp nếu nó thỏa mãn các điều kiện sau:

• k lẻ.
• ~c_{(2*j-1)}~ < ~c_{(2*j)}~ và ~c_{(2*j+1)}~ < ~c_{(2*j)}~ với ∀j: 1 < 2*j < k.
• ~c_1~, ~c_2~,…,~c_k~ là dãy con của dãy ~a_1~, ~a_2~,…,~a_n~.
• ~c_1~, ~c_2~,…,~c_k~ là dãy con của dãy ~b_1~, ~b_2~,…,~b_m~.

Yêu cầu: Tìm độ dài lớn nhất của dãy con đẹp và số lượng dãy con đẹp khác nhau có độ dài lớn nhất.

Dữ liệu vào:

• Dòng đầu c hứa số nguyên dương n (1 ≤ n ≤ 10000).
• Dòng thứ hai ghi n số nguyên ~a_1~, ~a_2~,…,~a_n~ (1 ≤ ~a_i~ ≤ 20000,i = 1..n).
• Dòng thứ ba chứa số nguyên dương m (1 ≤ m ≤ 10000).
• Dòng cuối ghi m số nguyên ~b_1~, ~b_2~,…,~b_m~ (1 ≤ ~b_i~ ≤ 20000,i = 1..m).

Dữ liệu ra:

• Ghi một dòng gồm hai số là độ dài lớn nhất của dãy con đẹp và số lượng dãy con đẹp khác nhau có độ dài lớn nhất mod (~10^9~ + 9). Trong trường hợp không có câu trả lời, dữ liệu in ra hai số 0 0.

Ví dụ:

INPUT

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

OUTPUT

3  6

Các ràng buộc:

• Thời gian: 2s/test
• 25% tổng số test có 1 ≤ n ≤ 20,1 ≤ m ≤ 10.
• 25% tổng số test tiếp theo có 1 ≤ n ≤ 1000,1 ≤ m ≤ 20.
• 25% tổng số test tiếp theo có 1 ≤ n,m ≤ 500.
• 25% tổng số test cuối có 1 ≤ n,m ≤ ~10^4~.