D. Day of rain
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

On a gray and rainy day, Lautaro and Fiorella decided to take shelter under the eaves of the gallery and spend the afternoon playing brisca, a traditional card game. But since their deck of cards was wet, they replaced it with a very strange one they found among their grandfather's old books. This deck has some peculiarities:

  • Each card has a suit and a value.
  • There are no two distinct cards with the same suit and value.
  • The deck contains an arbitrary number of distinct suits, not necessarily the four usual suits.

The game of brisca is played in rounds. In each round, both players take a card from the deck, then the two cards are compared to decide who wins the round, and finally, the two cards are discarded. In the first round, Lautaro plays first, and then, the winner of a round plays first in the following round. The game ends when there are no more cards left in the deck.

At the beginning of the game, a trump suit is chosen, which beats any other suit in the deck. The rules for deciding the winner of each round take this trump suit into account and are as follows:

  1. If both cards are of the same suit, the one who played the card of higher value wins (remember that all cards are distinct, so there can be no ties).
  2. If the cards are of different suits, but one is the trump suit, the one who played the trump wins.
  3. If the cards are of different suits and neither is the trump suit, the one who played first in the round wins.

Lautaro, always meticulous, noted in his notebook which card each player played in each round and how many rounds each one won. However, he forgot to note which was the trump suit. Luckily, you can help him. Your task is to determine which suit in the deck could have been the trump, such that the number of rounds won by each player matches what Lautaro recorded.

Input

The first line contains two integers $$$M$$$ and $$$N$$$ ($$$0 \leq M, N \leq 10^5$$$ and $$$M + N \ge 1$$$), indicating the number of rounds won by Lautaro and Fiorella respectively.

Each of the following $$$M + N$$$ lines describes the cards played in a round with four values: $$$V$$$, $$$P$$$, $$$W$$$, and $$$Q$$$. The values $$$V$$$ and $$$P$$$ describe the card played by Lautaro in the round, while $$$W$$$ and $$$Q$$$ describe Fiorella's card. The values $$$V$$$ and $$$W$$$ are integers ($$$1 \leq V, W \leq 10^9$$$) representing the value of the cards, while $$$P$$$ and $$$Q$$$ are non-empty strings of at most ten characters formed by uppercase letters, indicating the suits. The rounds are described in the order they were played.

Output

A string reporting the suit that was chosen as trump, which must be one of the suits that appear in the input.

If there is more than one possible suit, any of them will be considered valid.

If no suit from the input could have been chosen as trump, the character "*" (asterisk) should be printed.

Examples
Input
1 1
2 ROJO 3 NARANJA
1 AZUL 4 BLANCO
Output
BLANCO
Input
0 2
3 PLATA 2 PLATA
8 BRONCE 1 ORO
Output
*
Input
4 3
1 COCO 2 FRUTILLA
8 FRUTILLA 4 PERA
4 MANZANA 3 PERA
100 ANANA 10 ANANA
5 PERA 5 FRUTILLA
2 COCO 9 FRUTILLA
3 FRUTILLA 99 PERA
Output
FRUTILLA
Note

In the first example, if "BLANCO" is the trump suit, Lautaro wins the first round (because he plays first), while Fiorella wins the second (because she plays trump). If another suit were trump, one of the two players would win both rounds.

In the second example, Lautaro wins the first round regardless of which suit is trump, so it is impossible for Fiorella to win both rounds. None of the suits could have been chosen as trump.

In the third example, "PERA" could also have been a valid response.