Problem Statement

Find a length-N string that satisfies all of the following conditions:

• Each character is - or =.
• It is a palindrome.
• It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---

Problem Statement

We have seven cards. The i-th card (i=1,\ldots,7) has an integer A_i written on it.
Determine whether it is possible to choose five of them so that the chosen cards form a full house.

A set of five cards is called a full house if and only if the following conditions are satisfied:

• For different integers x and y, there are three cards with x and two cards with y.

Constraints

• A_i is an integer between 1 and 13, inclusive.

Sample Input 1

1 4 1 4 2 1 3

Sample Output 1

Yes

For example, by choosing the cards (1,1,1,4,4), we can form a full house.

Sample Input 2

11 12 13 10 13 12 11

Sample Output 2

No

No five cards chosen from the seven cards form a full house.

Sample Input 3

7 7 7 7 7 7 7

Sample Output 3

No

Note that five identical cards do not form a full house.

Sample Input 4

13 13 1 1 7 4 13

Sample Output 4

Yes

Problem Statement

There are N people, labeled 1 to N. Person i has an integer A_i.

Among the people who satisfy the condition "None of the other N-1 people has the same integer as themselves," find the one with the greatest integer, and print that person's label.

If no person satisfies the condition, report that fact instead.

Constraints

• 1 \leq N \leq 3\times 10^5
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

9
2 9 9 7 9 2 4 5 8

Sample Output 1

9

Those who satisfy the condition are the persons labeled 4, 7, 8, and 9.
Their integers are 7, 4, 5, and 8, respectively, and the person with the largest integer is the person labeled 9.
Thus, the answer is 9.

Sample Input 2

4
1000000000 1000000000 998244353 998244353

Sample Output 2

-1

If no person satisfies the condition, print -1.

Problem Statement

There is an infinitely large two-dimensional grid, with a campfire at coordinate (0,0).
At time t=0, smoke exists only at cell (0,0).

You are given a length-N string S consisting of N, W, S, E. At times t=1,2,\dots,N, the following happen in order:

• Wind blows, and all the smoke present at that time moves as follows:
  • If the t-th character of S is N, smoke in cell (r,c) moves to cell (r-1,c).
  • If it is W, smoke in cell (r,c) moves to cell (r,c-1).
  • If it is S, smoke in cell (r,c) moves to cell (r+1,c).
  • If it is E, smoke in cell (r,c) moves to cell (r,c+1).
• If there is no smoke in cell (0,0), new smoke is generated at cell (0,0).

Takahashi is standing at cell (R,C).
For each integer 1 \le t \le N, determine if smoke exists at cell (R,C) at time t+0.5, and print the response according to the required format.

Constraints

• N is an integer between 1 and 200000, inclusive.
• S is a length N string consisting of N, W, S, E.
• R and C are integers between -N and N, inclusive.
• (R,C) \neq (0,0)

Sample Input 1

6 -2 1
NNEEWS

Sample Output 1

001010

At times 1.5,2.5,4.5,6.5, there is no smoke at cell (-2,1). At times 3.5,5.5, there is smoke at cell (-2,1).
Hence, output 001010.

In the figures below, taking cell (0,0) with the campfire as a reference, cell (r,c) is drawn:

• -r cells up if r < 0,
• r cells down if r \ge 0,
• -c cells left if c < 0,
• c cells right if c \ge 0.

The grid at time 0.5 looks like:

The grid at time 1.5 looks like:

The grid at time 2.5 looks like:

The grid at time 3.5 looks like:

The grid at time 4.5 looks like:

The grid at time 5.5 looks like:

The grid at time 6.5 looks like:

Sample Input 2

10 1 2
NEESESWEES

Sample Output 2

0001101011

Sample Input 3

20 -1 -2
WWNNWSWEWNSWWENSNWWN

Sample Output 3

00100111111000101111

Problem Statement

This problem is an interactive problem (in which your program and the judge system communicate via input and output).

You are given a tree G with N vertices numbered 1 to N. The i-th edge connects vertices U_i and V_i.

You will play a game with Takahashi using this tree G. First, you decide who is first and who is second. Then, starting from the first player, take turns performing the following operation:

• Choose a pair of integers (i,j) with 1 \leq i < j \leq N that satisfies both of the following conditions, then add an edge connecting vertices i and j to G.
  • G does not already have an edge connecting vertices i and j.
  • Adding an edge connecting vertices i and j does not create an odd cycle.

A player who cannot perform this operation loses, and the other player wins. Play this game against Takahashi and win.

Constraints

• 2 \leq N \leq 100
• 1 \leq U_i < V_i \leq N
• The given graph is a tree.
• All input values are integers.

Interaction

This is an interactive problem (in which your program and the judge system communicate via input and output).

First, read N and the edges of G from Standard Input, given in the following format:

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Then, decide whether you go first or second. If you choose first, print First; if second, print Second.

Then, the game begins.

On your turn, output the chosen pair (i,j) by printing two integers i and j in this order, separated by a space:

i j

On Takahashi's turn, two integers i,j will be given in order, separated by a space, via Standard Input:

i j

If (i,j)=(-1,-1), it means he can no longer make a move and you win. Immediately terminate your program in this case.
Otherwise, (i,j) is the pair of integers he has chosen.

Notes

• After each output, be sure to print a newline and flush Standard Output. Otherwise, you may get TLE.
• If you produce output in an incorrect format or your program ends prematurely, the judge result is indeterminate.
• Once the game finishes, terminate your program immediately. Otherwise, the judge result is indeterminate.

Sample Interaction

Problem Statement

Find one shortest palindrome that has S as its prefix.

Constraints

• S is a string of length between 1 and 500000, inclusive, consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

ABCBA

ABCBA is a shortest palindrome that has S= ABC as its prefix.

Sample Input 2

Z

Sample Output 2

Z

Z is a shortest palindrome that has S= Z as its prefix.

Sample Input 3

TREE

Sample Output 3

TREERT

TREERT is a shortest palindrome that has S= TREE as its prefix.

Problem Statement

You are given a simple undirected graph with N vertices and M edges, with vertices labeled 1 to N and edges labeled 1 to M. The i-th edge connects vertices U_i and V_i. Initially, G does not contain an odd cycle.

Takahashi and Aoki will play a game using this graph G. With Aoki going first, they take turns performing the following operation:

• Choose a pair of integers (i,j) with 1 \leq i < j \leq N that satisfies both of the following conditions, then add an edge connecting vertices i and j to G.
  • G does not already have an edge connecting vertices i and j.
  • Adding an edge connecting vertices i and j does not create an odd cycle.

A player who cannot perform this operation loses, and the other player wins.

Determine who wins when both players play optimally.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1 \leq U_i < V_i \leq N
• The given graph does not contain an odd cycle.
• The given graph does not contain multi-edges.
• All input values are integers.

Sample Input 1

4 3
1 2
2 3
3 4

Sample Output 1

Aoki

If Aoki (the first player) adds the edge (1,4), Takahashi (the second player) cannot move. Thus, Aoki wins.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

Takahashi

No matter how Aoki plays, Takahashi wins.

Sample Input 3

9 5
2 9
2 3
4 6
5 7
1 8

Sample Output 3

Aoki