Задача G. Праздники ≡

Условие

На планете в звездной системе Альфа Кентавра неделя состоит из $A$ дней, а год — из $B$ дней. Годы нумеруются последовательными натуральными числами: $1, 2, 3, \ldots$ Кроме того, годы с номерами $C_1,\,C_2, \ldots,\,C_N$ являются високосными и состоят из $(B+1)$ дней. В году дни с номерами $D_1,\,D_2, \ldots,\,D_M$ являются праздничными. Если праздник попадает на $(B+1)$-й день года, то он отмечается только в високосные годы. Первый день первого года является первым днем недели.

Один из жителей планеты решил устроиться на новую работу. В соответствии с заключенным трудовым договором он будет числиться на данной работе в течение $E$ дней, начиная с первого дня $1$-го года. По договору он имеет право выбрать один день недели (с $1$ по $A$), который будет для него выходным. Праздничные дни также считаются нерабочими. Житель хочет выбрать себе выходной день таким образом, чтобы за период действия договора у него было максимальное количество нерабочих дней.

Требуется написать программу, которая определяет искомый день недели и вычисляет соответствующее количество нерабочих дней.

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

В первой строке входного файла через пробел записаны числа $A$ и $B$ — количество дней в неделе и в невисокосном году соответственно ($1\le A \le 2500$, $1\le B \le 10000$). Во второй строке записано число $N$ — количество високосных лет, и в третьей — номера $C_1,\,C_2, \ldots,\,C_N$ високосных лет в возрастающем порядке ($0 \le N \le 5000$, $1 \le C_1 \lt C_2 \lt \ldots \lt C_N \le 10^7$). В следующей строке число $M$ — количество праздничных дней в году, и на новой строке — $D_1,\,D_2, \ldots,\,D_M$ в возрастающем порядке ($1 \le D_1 \lt D_2 \lt \ldots \lt D_M \le B+1$). В последней строке записано число $E$ ($1\le E \le 10^9$). Известно, что житель заключил контракт не более чем на $10^7$ лет.

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

В выходной файл выведите через пробел два числа — номер дня недели, который выгоднее всего сделать выходным, и соответствующее количество нерабочих дней за период действия договора. Если ответов несколько, то выведите любой из них.

Примеры тестов

7 13
1
2
2
1 14
29

1 8

3 9
0

3
1 4 7
19

2 13