H. Томительное ожидание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Анатолий договорился со Славой вместе доехать до нового автовокзала.

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

Известно, что Слава уже сел на нужный автобус и едет в направлении «A B» (то есть сначала он проедет остановку A, а уже потом остановку B).

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

Чтобы не замерзнуть, Анатолий решил сесть в первый подъехавший автобус и доехать до остановки A, чтобы подождать там. Но на остановке A теплее не стало, поэтому Анатолий запрыгнул в автобус, направлявшийся к остановке B...

Опишем процесс более формально:

  • Если Анатолий находится на остановке B, то он поедет к остановке A только в случае, если успеет приехать туда строго раньше, чем туда прибудет автобус со Славой.
  • Если Анатолий находится на остановке A, то он поедет к остановке B только в случае, если успеет приехать туда строго раньше, чем автобус со Славой прибудет к остановке A.

Известно, что все автобусы проезжают расстояние между остановками A и B (в одну и другую сторону) за d минут.

Также известно, что если Анатолий выйдет из автобуса во время t, то сесть в следующий автобус он сможет не ранее t + 1 (надо дорогу перейти, как минимум).

Зная время прибытия всех автобусов на остановку B, определите:

  • на какой остановке Анатолий сядет в автобус, в котором едет Слава;
  • на скольких автобусах успеет прокатиться Анатолий до момента встречи.
Входные данные

В первой строке содержатся через пробел целые числа n, m, d (1 ≤ n,  m ≤ 106,  1 ≤ d ≤ 106) — количество автобусов, едущих к остановке B со стороны остановки A, количество автобусов, едущих к остановке B с противоположной стороны и время проезда между остановками A и B, соответственно.

Во второй строке содержится через пробел n целых чисел a1, a2, ..., an (0 ≤ a1 < a2 < ... < an ≤ 106) — моменты времени, в которые к остановке B подъезжают автобусы, едущие со стороны остановки A.

Слава едет в последнем из этих автобусов.

В третьей строке содержится m целых чисел b1, b2, ..., bm (0 ≤ b1 < b2 < ... < bm ≤ 106) — моменты времени, в которые к остановке B подъезжают автобусы, едущие с противоположной стороны.

Выходные данные

В первой строке выведите через пробел символ и целое число:

  • символ A, если Анатолий сядет в автобус со Славой на остановке A, или символ B, если Анатолий сядет на остановке B;
  • количество автобусов, на которых к этому моменту проедет Анатолий.
Пример
Входные данные
5 6 4
8 15 24 26 30
1 7 10 16 22 27
Выходные данные
A 3
Примечание

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

Слава приедет на остановку B в момент времени 30, а на остановку A соответственно — в 30 - 4 = 26.

  • В момент времени 1 Анатолий сядет в автобус, следующий от B к A.
  • В момент времени 1 + 4 = 5 Анатолий доедет до остановки A.
  • В момент времени 15 - 4 = 11 Анатолий сядет в автобус, следующий от A к B.
  • В момент времени 15 Анатолий доедет до остановки B.
  • В момент времени 16 Анатолий сядет в автобус, следующий от B к A.
  • В момент времени 16 + 4 = 20 Анатолий доедет до остановки A.
  • Обратите внимание, что Анатолий не сможет сесть на автобус до остановки B в момент 24 - 4 = 20, так как на пересадку требуется минимум одна минута.
  • Также обратите внимание, что Анатолий не сможет сесть на автобус до остановки B в момент 26 - 4 = 22, так как в таком случае он прибудет на остановку B в момент времени 26 — Слава уже подъедет к остановке A в этот момент.
  • Соответственно, Анатолий дождётся Славу на остановке A, проехав на трёх автобусах.