Best Luggage Placement

Little S is about to start an exciting journey by boarding a high-speed train. The overhead luggage compartments in her coach come in two columns: the left column (denoted by 0) and the right column (denoted by 1). Each column contains n positions numbered from 1 to n from front to back.

The distance between any two positions with indices i and j (regardless of column) is defined as \(|i - j|\). Recall that \(|x|\) is defined as:

\[ |x| = \begin{cases} x, & \text{if } x \ge 0, \\ -x, & \text{if } x < 0. \end{cases} \]

Little S sits at position q in column p (where p = 0 or 1 and 1 \le q \le n). She wishes to place her luggage in an empty slot on the overhead compartments. Some slots are already occupied by other luggage and are not available.

Her objective is twofold:

1. Choose a free slot with the minimum possible distance from her seat (i.e. minimize \(|i - q|\)).
2. If there are two free slots with the same minimum distance but in different columns, she prefers the one in the same column as her seat.

If no empty slot is available, output -1.

inputFormat

The first line contains three integers n, p, and q where 1 \le n \le 10^5, p is either 0 or 1, and 1 \le q \le n. The next two lines describe the occupancy of the two columns. Each of these lines contains n integers. In each line, an integer 0 indicates that the slot is empty, and 1 indicates that the slot is occupied. The first of these lines corresponds to the left column (column 0) and the second line corresponds to the right column (column 1).

outputFormat

If a valid placement exists, output two integers separated by a space: the column (0 or 1) and the position index selected for the luggage. If no empty slot is available, output -1.

sample

5 0 3
0 1 0 0 1
1 0 0 1 0

0 3