As the Cards Fall

Limits: 2 sec., 512 MiB

Zenyk is a famous card player. Marichka wondered whether he is really that skilled, so she offered him a bet.

Zenyk gets \(n\) cards in his hand, and a deck of \(m\) cards lies on the table. Each card has either a positive integer or the symbol * written on it. To win the bet, Zenyk has to play exactly \(k\) cards from his hand and score at most \(s\) points.

At the start of the turn Zenyk has zero points. He chooses exactly \(k\) cards from his hand and plays each of them by the following rules:

• if a number is written on the card, it is added to his points;

• if * is written on the card, Zenyk takes the top card of the deck and plays it by the same rules. If the card taken also has * on it, Zenyk takes the next card of the deck.

All the cards taken from the deck are removed from it and cannot be used again. The cards taken from the deck do not count towards the \(k\) cards chosen from the hand. It is guaranteed that the deck has enough cards with numbers to finish the turn for any choice of \(k\) cards from the hand.

Zenyk knows which cards are in the deck, but he does not know their order. Help him find out whether he can choose exactly \(k\) cards from his hand so that he wins the bet whatever the order of the cards in the deck.

Input

The first line contains four integers \(n\), \(m\), \(k\) and \(s\) – the number of cards in the hand, the number of cards in the deck, the number of cards to choose from the hand, and the largest allowed number of points, respectively.

The second line contains \(n\) values separated by spaces – the cards in the hand. Each value is either the symbol * or a positive integer.

The third line contains \(m\) values separated by spaces – the cards in the deck, in the same format. The order of the values in this line does not determine the order of the cards in the deck.

Output

Print TAK if Zenyk can choose exactly \(k\) cards from his hand so that his points do not exceed \(s\) for any order of the deck, or NI otherwise.

Constraints

\(1 \le k \le n \le 2 \cdot 10^5\),

\(1 \le m \le 2 \cdot 10^5\),

\(1 \le s \le 10^9\),

each number on a card is from 1 to 1000,

the deck has at least \(\min(k, c)\) cards with numbers, where \(c\) is the number of cards with the symbol * in the hand.

Samples

Input (stdin) сopy	Output (stdout) сopy
6 4 3 10 * 2 10 * 8 * 1 5 3 *	TAK

Notes

In the example, Zenyk can choose the card with the number 2 and two cards with *. Whatever the order of the deck, the cards with numbers taken from the deck add at most \(5 + 3\) points. So he scores at most \(2 + 5 + 3 = 10\) points and wins the bet.