Республиканская олимпиада по информатике 2017 год, Павлодар

(Әдемі тізбек)

Ограничение по времени:

1.5 seconds

Ограничение по памяти:

16 megabytes

Тізбекше деп басқа тізбектен кейбір элементтерін өшіріп және басқа элементтердің орнын ауыстырмай алуға болатын тізбекті атаймыз. Сізге көлемі $n$: $a_1, a_2, \ldots, a_n$ және көлемі $m$: $b_1, b_2, \ldots, b_m$ болатын екі тізбек берілген. $k$ бүтін саннан тұратын $c_1, c_2, \ldots, c_k$ тізбегін әдемі деп атаймыз егерде төмендегі шарттар орындалса: \begin{itemize}

k тақ сан.

Барлық $1 < 2 * j < k$ үшін $c_{2*j-1} < c_{2 * j}$ және $c_{2*j+1} < c_{2 * j}$.

$c_1, c_2, \ldots, c_k$ тізбегі $a_1, a_2, \ldots, a_n$ тізбегінің тізбекшесі.

$c_1, c_2, \ldots, c_k$ тізбегі $b_1, b_2, \ldots, b_m$ тізбегінің тізбекшесі.

\end{itemize} Ең үлкен әдемі тізбектің көлемін және ең үлкен әдемі әр түрлі тізбектің санын $10^9 + 9$ санына бөлгендегі қалдығын табу керек.

Формат входного файла

Бірінші жолда бір бүтін сан берілген $n$ ($1 \le n \le 10^4$)~— $a$ тізбегінің көлемі. Екінші жолда $n$ бүтін сан жазылған $a_i$ ($1 \le a_i \le 20000$)~— $a$ тізбегі. Үшінші жолда бір бүтін сан берілген $m$ ($1 \le m \le 10^4$)~— $b$ тізбегінің көлемі. Төртінші жолда $m$ бүтін сан жазылған $b_i$ ($1 \le b_i \le 20000$)~— $b$ тізбегі. Екі тізбектегі сандар бір бос орын арқылы берілген.

Формат выходного файла

Екі бүтін сан шығарыңыз - берілген есептің жауабын. Егер шешімі жоқ болса екі нөл шыгарыңыз.

Система оценки

Есеп төрт бөлімнен тұрады:

1. $1 \leq n \leq 20$, $1 \le m \le 10$. Бұл бөлім $9$ ұпайға бағаланады.
2. $1 \leq n \leq 1000$, $1 \le m \le 20$. Бұл бөлім $9$ ұпайға бағаланады.
3. $1 \leq n \leq 500$, $1 \le m \le 500$. Бұл бөлім $28$ ұпайға бағаланады.
4. $1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Бұл бөлім $54$ ұпайға бағаланады.

Пример:

s Вход

1
1
1
2

Ответ

0 0

Вход

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

Ответ

3 6

Вход

4
1 1 3 2
4
1 3 2 2

Ответ

3 1

( Aidos Nurmash )