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},\ \ldots,\ a_{n}\) và \(b_{1}\), \(b_{2},\ \ldots,\ b_{m}\). Dãy \(c_{1}\), \(c_{2},\ \ldots,\ 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 \(\forall j:1 < 2*j < k\).

• \(c_{1}\), \(c_{2},\ \ldots,\ c_{k}\) là dãy con của dãy \(a_{1}\), \(a_{2},\ \ldots,\ a_{n}\).

• \(c_{1}\), \(c_{2},\ \ldots,\ c_{k}\) là dãy con của dãy \(b_{1}\), \(b_{2},\ \ldots,\ 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 \leq n \leq 10\ 000).\)

+ Dòng thứ hai ghi \(n\) số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) \((1 \leq a_{i} \leq 20\ 000,\ \ i = 1..n)\).

+ Dòng thứ ba chứa số nguyên dương \(m\ (1 \leq m \leq 10\ 000).\)

+ Dòng cuối ghi \(m\) số nguyên \(b_{1},\ b_{2},\ \ldots,\ b_{m}\) \((1 \leq b_{i} \leq 20\ 000,\ \ 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 \(\mathbf{mod\ }\mathbf{(10}^{\mathbf{9}}\mathbf{+ 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ụ:

Các ràng buộc:

• 25% tổng số test có \(1 \leq n \leq 20,\ 1 \leq m \leq 10\).

• 25% tổng số test tiếp theo có \(1 \leq n \leq 1000,1 \leq m \leq 20\).

• 25% tổng số test tiếp theo có \(1 \leq n,m \leq 500\).

• 25% tổng số test cuối có \(1 \leq n,\ m \leq 10^{4}.\)