I - 簡易オマハポーカー 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

1, \dots, N と番号付けられた N 人のプレイヤーが机を囲んでカードゲームで対戦します。カードは 26 種類あり、それぞれ A、B、…、Z が書かれています。カードは机の上に 5 枚置かれ、各プレイヤーに 4 枚配られます。

机の上に置かれたカードは長さ 5 の文字列 X で表され、プレイヤー i \, (1 \leq i \leq N) に配られたカードは長さ 4 の文字列 S_i で表されます。X, S_1, \dots, S_N は全て英大文字からなり、それぞれの文字はカードがどの種類のものであるかを表しています。

各プレイヤーは、自分に配られたカードから 2 枚を、机の上のカードから 3 枚を選んで 5 枚のカードの組み合わせを作ります。この組み合わせをそのプレイヤーのハンドと呼びます。

各 i \, (1 \leq i \leq N) について、n_i および c_i を次のように定めます。

  • プレイヤー i のハンドに存在する同じ種類のカードのうち、最も枚数が多いものが n 枚あり、書かれている文字が c であるとする。ただし、そのようなものが複数考えられる場合は、c がアルファベット順で最も小さくなるようにする。この (n, c) について、n_i = n, c_i = c と定める。

プレイヤー A, B \, (A \neq B) のどちらが優れているかは、次のようにして定まります。

  • n_A > n_B ならば A の方が優れており、n_B > n_A ならば B の方が優れている。
  • n_A = n_B の場合は次のように定まる。
    • c_A \neq c_B のとき、c_A がアルファベット順で c_B より小さければ A の方が優れており、大きければ B の方が優れている。
    • c_A = c_B のとき、A < B ならば A の方が優れており、B < A ならば B の方が優れている。

全てのプレイヤーが最適に行動するとき、最も優れたプレイヤーは誰になるかを求めてください。すなわち、以下の条件が成り立つ i を求めてください。

  • 全ての j \neq i に対し、プレイヤー i がプレイヤー j より優れている。

制約

  • 2 \leq N \leq 1000
  • N は整数
  • X は英大文字からなる長さ 5 の文字列
  • S_i \, (1 \leq i \leq N) は英大文字からなる長さ 4 の文字列

入力

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

N
X
S_1
\vdots
S_N

出力

答えを出力せよ。

入力例 1

3
AABCD
DDBC
ABBQ
XYZA

出力例 1

2

ここでは、カードに書かれた英大文字を 5 つ並べた文字列としてハンドを表すことにします。

たとえば、プレイヤー 1 が手元から D、B が書かれたカードを選び、机の上から A、B、C　が書かれたカードを選んだとします。このとき、ハンドは DBABC あるいは ABBCD のように表されます (どちらも同じハンドを表します) 。

以下に (最適とは限らない) プレイの一例を示します。

  • プレイヤー 1 が BCDDD、プレイヤー 2 が AABBQ というハンドを作った場合、n_1 = 3、c_1 = D、n_2 = 2、c_2 = A となります。この場合、プレイヤー 1 の方が優れています。
  • プレイヤー 1 が BCDDD、プレイヤー 2 が AAABB というハンドを作った場合、n_1 = 3、c_1 = D、n_2 = 3、c_2 = A となります。この場合、プレイヤー 2 の方が優れています。
  • プレイヤー 2 が AAABB、プレイヤー 3 が AAABZ というハンドを作った場合、n_2 = 3、c_2 = A、n_3 = 3、c_3 = A となります。この場合、プレイヤー 2 の方が優れています。

3 人のプレイヤーの最適な行動の一例は、プレイヤー 1 が ABDDD、プレイヤー 2 が AAABB、プレイヤー 3 が AAABZ というハンドを作ることです。このとき、プレイヤー 2 はプレイヤー 1, 3 の両方よりも優れているので、答えは 2 となります。

入力例 2

4
ABBDE
ADDZ
BEEZ
DDDD
BDDE

出力例 2

2

Problem Statement

N players numbered 1, \dots, N sitting around a table play a card game. There are 26 kinds of cards, each of which has A, B, …, or Z written on it. Five cards are placed on the table, and four are dealt to each player.

The cards on the table are represented by a string X of length five, and the cards dealt to player i \, (1 \leq i \leq N) are represented by a string S_i of length four. X, S_1, \dots, and S_N consist of uppercase English letters, representing the kinds of the cards.

Each player chooses two cards from those dealt to the player and three from those on the table to make a set of five cards. This set is called the player's hand.

For each i \, (1 \leq i \leq N), define n_i and c_i as follows:

  • let n_i = n and c_i = c, where n is the maximum integer such that player i's hand contains n cards of the same kind, and c is the character written on them. If there are multiple candidates, choose the alphabetically smallest c.

The superiority between two players A and B (A \neq B) is determined as follows:

  • A is superior if n_A > n_B, and B is superior if n_B > n_A.
  • If n_A = n_B, it is determined as follows:
    • If c_A \neq c_B, A is superior if c_A is alphabetically smaller than c_B, and B is superior if it is larger.
    • If c_A = c_B, A is superior if A < B, and B is superior if B > A.

Find the supreme player if all players play optimally. In other words, find i such that:

  • for all j \neq i, player i is superior to player j.

Constraints

  • 2 \leq N \leq 1000
  • N is an integer.
  • X is a string of length 5 consisting of uppercase English letters.
  • S_i \, (1 \leq i \leq N) is a string of length 4 consisting of uppercase English letters.

Input

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

N
X
S_1
\vdots
S_N

Output

Print the answer.

Sample Input 1

3
AABCD
DDBC
ABBQ
XYZA

Sample Output 1

2

Here, a hand is represented by a string consisting of the five uppercase English letters written on the cards.

For example, suppose that player 1 chooses the cards with D and B from the dealt ones and those with A, B, and C from those on the table; then the hand is represented by, for instance, DBABC or ABBCD (both represent the same hand).

The following are examples of (not necessarily optimal) plays.

  • If player 1 makes a hand BCDDD and player 2 makes AABBQ, we have n_1 = 3, c_1 = D, n_2 = 2, and c_2 = A. In this case, player 1 is superior.
  • If player 1 makes a hand BCDDD and player 2 makes AAABB, we have n_1 = 3, c_1 = D, n_2 = 3, and c_2 = A. In this case, player 2 is superior.
  • If player 2 makes a hand AAABB and player 3 makes AAABZ, we have n_2 = 3, c_2 = A, n_3 = 3, and c_3 = A. In this case, player 2 is superior.

One possible optimal hand of each player is as follows: player 1 makes ABDDD, player 2 makes AAABB, and player 3 makes AAABZ. Since player 2 is superior to both players 1 and 3, the answer is 2.

Sample Input 2

4
ABBDE
ADDZ
BEEZ
DDDD
BDDE

Sample Output 2

2