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\ast j-1)}$ < $c_{(2\ast j)}$ và $c_{(2\ast j+1)}$ < $c_{(2\ast 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$.