Problem Statement

The Eastern Army and the Western Army are at war in a certain capital.

Takahashi recorded information about the fighting forces as a string S.
S contains only the characters E and W, and the number of Es in S equals the number of soldiers in the Eastern Army, and the number of Ws equals the number of soldiers in the Western Army.

Given the string S that Takahashi recorded, output East if the Eastern Army has more soldiers than the Western Army, or West if the Western Army has more soldiers than the Eastern Army.

The length of S is guaranteed to be odd. Thus, it can be proved that exactly one of the two armies strictly outnumbers the other (that is, the two armies cannot have the same number of soldiers).

Constraints

• S is a string of length between 1 and 99, inclusive, consisting of E and W.
• The length of S is odd.

Sample Input 1

EEWEW

Sample Output 1

East

S contains three Es and two Ws, so the Eastern Army has three soldiers and the Western Army has two soldiers.
Since the Eastern Army has more soldiers than the Western Army, output East.

Sample Input 2

WWWWWWW

Sample Output 2

West

S contains zero Es and seven Ws, so the Eastern Army has zero soldiers and the Western Army has seven soldiers.
Since the Western Army has more soldiers than the Eastern Army, output West.

Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

There are N cups, each containing a colorless and transparent liquid.
Specifically, the i-th (1\leq i\leq N) cup contains A_i ml of liquid.
It is known that exactly K of these cups contain sake (rice wine), and the rest contain water.
However, it is not known which cups contain sake.

Takahashi can choose some (one or more) cups and drink all the liquid in them.
Find the minimum number of cups he needs to choose to ensure he drinks at least X ml of sake, regardless of which cups contain sake.
If such a choice is impossible, print -1.

Constraints

• 1 \leq K \leq N \leq 3\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 3\times 10^{14}
• All input values are integers.

Sample Input 1

3 2 5
10 6 8

Sample Output 1

2

Consider the case where Takahashi chooses the first and third cups and drinks them.

Two out of the three cups contain sake, so the following three cases are possible:

• If the first and second cups contain sake

He drinks 10 ml of sake and 8 ml of water.

• If the first and third cups contain sake

He drinks 18 ml of sake.

• If the second and third cups contain sake

He drinks 8 ml of sake and 10 ml of water.

Thus, in all cases, he can drink at least 5 ml of sake.
On the other hand, it is impossible to satisfy the condition by choosing only one cup without knowing which cups contain sake.

Therefore, print 2.

Sample Input 2

2 1 8
6 10

Sample Output 2

-1

If the first cup contained sake, it is impossible to drink 8 ml or more of sake no matter which cups are chosen.
Therefore, print -1.

Sample Input 3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5