You have been convinced to play poker at a very suspicious casino.

Luckily, you have obtained the order of the deck produced by the shuffling machine. Unfortunately, before dealing, the dealer cuts the deck exactly once. When a deck is cut, it is split into a top segment and a bottom segment, then the bottom segment is placed on top. The relative order of the cards inside each segment is unchanged.

After the cut, the dealer gives one card to each player from player ~1~ to player ~P~, then gives each player a second card in the same order. You know your position at the table and the two cards you receive, in the order they are dealt.

Determine the two-card hand of every player.

Input

The first line contains three integers ~N~, ~P~, and ~S~ ~(2 \le 2P \le N \le 2 \times 10^5,\ 1 \le S \le P)~: the number of cards in the deck, the number of players, and your position at the table.

The second line contains ~N~ distinct integers ~d_1, d_2, \dots, d_N~ ~(1 \le d_i \le N)~, the order of the deck before it is cut. Each integer from ~1~ to ~N~ appears exactly once.

The third line contains two distinct integers ~a~ and ~b~ ~(1 \le a,b \le N)~: your hand, in the order the cards are dealt to you.

It is guaranteed that there is a valid cut of the deck that gives you this hand.

Output

Output ~P~ lines. On line ~i~, output the two cards dealt to player ~i~, in the order they are dealt.

Example

Input 1

10 3 1
1 2 3 4 5 6 7 8 9 10
1 4

Output 1

1 4
2 5
3 6

Explanation: If the dealer cuts zero cards from the top, the deck remains 1 2 3 4 5 6 7 8 9 10. The first three cards go to players 1, 2, and 3, then the next three cards are dealt in the same order. Therefore player 1 receives 1 4, player 2 receives 2 5, and player 3 receives 3 6.

Input 2

12 4 3
1 2 3 4 5 6 7 8 9 10 11 12
11 3

Output 2

9 1
10 2
11 3
12 4

Explanation: The dealer cuts the deck between cards 8 and 9, making the new top of the deck 9. The dealt deck begins 9 10 11 12 1 2 3 4, so player 3 receives 11 and then 3.