H. Tiring Wait
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anatoly agreed with Slava to travel together to the new bus station.

The guys agreed to go together either from stop A or from the next stop B.

It is known that Slava has already boarded the necessary bus and is heading in the direction of "A B" (that is, he will first pass stop A and then stop B).

Anatoly arrived at stop B earlier than Slava but quickly realized that he misjudged the weather forecast — a heavy rain began with a piercing cold wind.

To avoid freezing, Anatoly decided to take the first bus that arrived and go to stop A to wait there. However, it didn't get any warmer at stop A, so Anatoly jumped on a bus heading to stop B...

Let's describe the process more formally:

  • If Anatoly is at stop B, he will go to stop A only if he can arrive there strictly earlier than the bus with Slava arrives.
  • If Anatoly is at stop A, he will go to stop B only if he can arrive there strictly earlier than the bus with Slava arrives at stop A.

It is known that all buses travel the distance between stops A and B (in both directions) in d minutes.

It is also known that if Anatoly gets off the bus at time t, he can board the next bus no earlier than t + 1 (he needs to cross the road, at least).

Knowing the arrival times of all buses at stop B, determine:

  • at which stop Anatoly will board the bus that Slava is on;
  • how many buses Anatoly will manage to ride before they meet.
Input

The first line contains space-separated integers n, m, d (1 ≤ n,  m ≤ 106,  1 ≤ d ≤ 106) — the number of buses going to stop B from stop A, the number of buses going to stop B from the opposite side, and the travel time between stops A and B, respectively.

The second line contains space-separated n integers a1, a2, ..., an (0 ≤ a1 < a2 < ... < an ≤ 106) — the moments in time when buses coming from stop A arrive at stop B.

Slava is on the last of these buses.

The third line contains m integers b1, b2, ..., bm (0 ≤ b1 < b2 < ... < bm ≤ 106) — the moments in time when buses coming from the opposite side arrive at stop B.

Output

In the first line, output a space-separated character and an integer:

  • the character A if Anatoly boards the bus with Slava at stop A, or the character B if Anatoly boards at stop B;
  • the number of buses Anatoly has ridden by that moment.
Example
Input
5 6 4
8 15 24 26 30
1 7 10 16 22 27
Output
A 3
Note

First test example

Slava will arrive at stop B at time 30, and at stop A respectively at 30 - 4 = 26.

  • At time 1, Anatoly will board the bus going from B to A.
  • At time 1 + 4 = 5, Anatoly will arrive at stop A.
  • At time 15 - 4 = 11, Anatoly will board the bus going from A to B.
  • At time 15, Anatoly will arrive at stop B.
  • At time 16, Anatoly will board the bus going from B to A.
  • At time 16 + 4 = 20, Anatoly will arrive at stop A.
  • Note that Anatoly will not be able to board the bus to stop B at time 24 - 4 = 20, as he needs at least one minute to transfer.
  • Also, note that Anatoly will not be able to board the bus to stop B at time 26 - 4 = 22, as in that case he would arrive at stop B at time 26 — Slava will already arrive at stop A at that moment.
  • Consequently, Anatoly will wait for Slava at stop A, having ridden on three buses.