### Chef and Linear Chess Problem Code: LINCHESS

### Read problem statements in Hindi, Bengali, Mandarin Chinese, Russian, and Vietnamese as well.

Chef wants to play a game of

*linear chess*on a one-dimensional board ― an infinite row of squares numbered by positive integers. In this game, he has a pawn, which is initially at a square . There are also other people (numbered through ); Chef can choose one of them to play against. For each valid , the -th player would play in the following way:- Take a pawn and place it on a square .
- Repeat the following move any number of times: move the pawn from its current square squares forward, i.e. from a square , this player's pawn is moved to the square .
- If this player moves their pawn to the square with Chef's pawn, then Chef's pawn is
*captured*and he loses the game.

Unfortunately, Chef cannot move his pawn during the game, making him an easy target for other players. Given the starting positions of all players, find a player who can capture Chef's pawn in the smallest number of moves or determine that no player can capture his pawn.

### Input

- The first line of the input contains a single integer denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains two space-separated integers and .
- The second line contains space-separated integers .

### Output

For each test case, print a single line containing one integer ― the starting square of one player that can beat Chef in the smallest number of turns, or if no player can beat him.

If there are multiple solutions, you may find any one.

### Constraints

- for each valid
- are pairwise distinct

### Subtasks

Subtask #1 (100 points): original constraints

### Example Input

```
2
4 6
4 3 2 8
4 7
4 3 2 8
```

### Example Output

```
3
-1
```

### Explanation

Example case 1: The player who starts at the position can move to square and then to square . The player who starts at the position can move to square . The player at position can capture Chef's pawn in turns, whereas the player at position can capture Chef's pawn in turn. Therefore, the answer is .

Example case 2: No player can capture Chef's pawn.

## Comments

## Post a Comment

Please give us your valuable feedback