B - Trick Taking Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

プレイヤー 1 、プレイヤー 2 、\ldots 、プレイヤー N と番号がつけられた N 人のプレイヤーがカードゲームで対戦します。
各プレイヤーはカードを 1 枚場に出します。

各カードは色と値の 2 つの属性を持ち、どちらの属性も正整数で表されます。
i = 1, 2, \ldots, N について、プレイヤー i が場に出したカードの色は C_i であり、値は R_i です。 R_1, R_2, \ldots, R_N はすべて異なります。

N 人のプレイヤーの中から 1 人の勝者を下記の方法で決めます。

  • 色が T であるカードが 1 枚以上場に出された場合、色が T であるカードのうち値が最大のものを出したプレイヤーが勝者である。
  • 色が T であるカードが場に 1 枚も出されなかった場合、プレイヤー 1 が出したカードと同じ色のカードのうち値が最大のものを出したプレイヤーが勝者である。（プレイヤー 1 自身も勝者となり得ることに注意してください。）

勝者となるプレイヤーの番号を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • i \neq j \implies R_i \neq R_j
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

出力

答えを出力せよ。

入力例 1

4 2
1 2 1 2
6 3 4 5

出力例 1

4

色が 2 であるカードが 1 枚以上場に出されています。 よって、色が 2 であるカードのうち値が最大の 5 のカードを出した、プレイヤー 4 が勝者です。

入力例 2

4 2
1 3 1 4
6 3 4 5

出力例 2

1

色が 2 であるカードが 1 枚も場に出されていません。 よって、プレイヤー 1 が出したカードの色と同じ色（すなわち色 1 ）のカードのうち値が最大の 6 のカードを出した、プレイヤー 1 が勝者です。

入力例 3

2 1000000000
1000000000 1
1 1000000000

出力例 3

1

Score : 200 points

Problem Statement

N players with ID numbers 1, 2, \ldots, N are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For i = 1, 2, \ldots, N, the card played by player i has a color C_i and a rank R_i. All of R_1, R_2, \ldots, R_N are different.

Among the N players, one winner is decided as follows.

  • If one or more cards with the color T are played, the player who has played the card with the greatest rank among those cards is the winner.
  • If no card with the color T is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player 1 is the winner. (Note that player 1 may win.)

Print the ID number of the winner.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T \leq 10^9
  • 1 \leq C_i \leq 10^9
  • 1 \leq R_i \leq 10^9
  • i \neq j \implies R_i \neq R_j
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N T
C_1 C_2 \ldots C_N
R_1 R_2 \ldots R_N

Output

Print the answer.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color 2 are played. Thus, the winner is player 4, who has played the card with the greatest rank, 5, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color 2 is played. Thus, the winner is player 1, who has played the card with the greatest rank, 6, among the cards with the color of the card played by player 1 (color 1).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1