Задача I. В движении
Задачу добавил: alef
Успешно сдано решений: 2
Тем временем Стив получил сообщение, в котором ему предлагали передать некую информацию. По мнению автора сообщения, эта информация обязательно заинтересует Стива. Незнакомец не просил ни денег, ни услуг взамен, а встретиться предложил в трамвае.
Незнакомец сообщил Стиву бортовой номер трамвая. Стив должен был сесть в последнюю дверь последнего вагона этого трамвая на остановке, которую мы условно назовём остановкой A, или на следующей после неё остановке, которую мы условно назовём остановкой B.
Павильон на остановке B совсем не защищал от пронизывающего ветра. Стив смотрел на экран: до прибытия трамвая с нужным бортовым номером было ещё порядочно времени. Немного поразмышляв, Стив сел в первый подошедший трамвай, который ехал по направлению к остановке A...
Опишем происходящее более формально.
В момент времени t = 0 Стив находится на остановке B. В его распоряжении имеется список трамваев, которые прибывают на остановку B и будут двигаться в сторону остановки A, а также список трамваев, которые прибывают на остановку B со стороны остановки A. Для каждого трамвая известно, через сколько времени он прибудет на остановку B (время отсчитывается от 0).
Расстояние между остановками B и A (оно же между A и B) трамвай проезжает за время d.
Находясь на остановке B, Стив оценивает время, за которое он может добраться до остановки A. Если, сев на первый идущий в сторону остановки A трамвай, он доберётся до остановки A строго раньше, чем трамвай с незнакомцем, Стив сядет на трамвай и проедет эту остановку.
Находясь на остановке A, Стив оценивает время, которое ему предстоит ожидать трамвай с незнакомцем. Если, сев на первый идущий в сторону остановки B трамвай, он доберётся до остановки B строго раньше, чем на остановку B прибудет трамвай с незнакомцем, Стив сядет на трамвай и проедет эту остановку.
Так будет продолжаться до тех пор, пока Стив не сядет в трамвай, в котором едет незнакомец.
Высадка и посадка занимают ненулевое время, поэтому если Стив приехал на остановку в момент времени t, то сесть на следующий трамвай он сможет не ранее, чем в момент времени t + 1.
Ваша задача — определить, на какой остановке Стив сядет в трамвай с незнакомцем, и на скольких трамваях к этому моменту он проедет.
В первой строке содержатся целые числа 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, а также количество трамваев, на которых к этому моменту проедет Стив.
4 5 4
8 15 24 30
1 7 10 16 27
A 3