Hide

Problem K
Einvígi

Languages en is
/problems/einvigi/file/statement/en/img-0001.jpg
A duel between two soldiers

Tómas is a great fan of war games. His favorite game these days is Einvígi margra. In the game two players battle one another. Each battle consists of a series of duels.

Tómas has $n$ soldiers, each denoted by a strength $a_i$. Tómas’ opponent also has $n$ soldiers, each denoted by a strength $b_i$.

The duels proceed with Tómas’ $i$-th soldier fighting the $i$-th soldier of his opponent. Tómas wins the duel if $a_i > b_i$, it’s a tie of $a_i = b_i$ and his opponent wins if $a_i < b_i$. The duels proceed in ascending order; first $a_1$ and $b_1$ duel, then $a_2$ and $b_2$ and so on until $a_n$ and $b_n$ have fought.

Tómas wins the battle if he wins more duels than his opponent.

Tómas has just bought an expansion pack for the game and thus has one Mega serum. The Mega serum has the effect that if Tómas uses it the strength of his soldiers will increase by $k$ in the next $m$ duels.

Tómas isn’t sure when he should use the Mega serum. If he chooses the best possible moment, can Tómas win the battle?

Input

The first line of the input contains three integers $n, m, k$ where $1 \le m \le n \le 10^5$, $1 \le k \le 10^7$. The second line of the input contains $n$ integers $a_1, a_2, \dotsc , a_n$, where $1 \le a_i \le 10^7$. The third line of the input contains $n$ integers $b_1, b_2, \dotsc , b_n$, where $1 \le b_i \le 10^7$.

Output

If Tómas can win the battle, print the earliest time he could use the Mega serum and win the battle. If he can’t win, instead print Neibb.

Scoring

Group

Points

Constraints

1

50

$1 \le m \le n \le 1\, 000$, $1 \le k, a_i \le 100$

2

50

No further constraints

Sample Input 1 Sample Output 1
3 2 1
3 2 1
2 2 1
0
Sample Input 2 Sample Output 2
5 2 100
1 1 1 1 1
101 101 101 1 1
Neibb