Problem Statement

You are given a string S consisting of lowercase English letters.

Uppercase each character of S and print the resulting string T.

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

• First, he painted the part from X=L_1 to X=R_1 red.
• Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

• 0\leq L_1<R_1\leq 100
• 0\leq L_2<R_2\leq 100
• All values in input are integers.

Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

Problem Statement

There are N rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.

Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.

Constraints

• 2\leq N\leq 100
• 0\leq A_i<B_i\leq 100
• 0\leq C_i<D_i\leq 100
• All input values are integers.

Sample Input 1

3
0 5 1 3
1 4 0 5
2 5 2 4

Sample Output 1

20

The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.

Sample Input 2

2
0 100 0 100
0 100 0 100

Sample Output 2

10000

Note that different sheets may cover the same region.

Sample Input 3

3
0 1 0 1
0 3 0 5
5 10 0 10

Sample Output 3

65

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

Problem Statement

Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.

A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.

Find the index of the best submission.

Constraints

• 1 \leq N \leq 10^5
• S_i is a string consisting of lowercase English characters.
• S_i has a length between 1 and 10, inclusive.
• 0 \leq T_i \leq 10^9
• N and T_i are integers.

Sample Input 1

3
aaa 10
bbb 20
aaa 30

Sample Output 1

2

We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.

Sample Input 2

5
aaa 9
bbb 10
ccc 10
ddd 10
bbb 11

Sample Output 2

2

Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.

Sample Input 3

10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3

Sample Output 3

8

Problem Statement

This problem is an easier version of Problem G.

There is a slot machine with three reels.
The arrangement of symbols on the i-th reel is represented by the string S_i. Here, S_i is a string of length M consisting of digits.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can either choose and press one button or do nothing exactly t seconds after the reels start spinning.
If he presses the button corresponding to the i-th reel exactly t seconds after the reels start spinning, the i-th reel will stop and display the ((t \bmod M)+1)-th character of S_i.
Here, t \bmod M denotes the remainder when t is divided by M.

Takahashi wants to stop all the reels so that all the displayed characters are the same.
Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved.
If this is impossible, report that fact.

Constraints

• 1 \leq M \leq 100
• M is an integer.
• S_i is a string of length M consisting of digits.

Sample Input 1

10
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can stop each reel as follows so that 6 seconds after the reels start spinning, all the reels display 8.

• Press the button corresponding to the second reel 0 seconds after the reels start spinning. The second reel stops and displays 8, the ((0 \bmod 10)+1=1)-st character of S_2.
• Press the button corresponding to the third reel 2 seconds after the reels start spinning. The third reel stops and displays 8, the ((2 \bmod 10)+1=3)-rd character of S_3.
• Press the button corresponding to the first reel 6 seconds after the reels start spinning. The first reel stops and displays 8, the ((6 \bmod 10)+1=7)-th character of S_1.

There is no way to make the reels display the same character in 5 or fewer seconds, so print 6.

Sample Input 2

20
01234567890123456789
01234567890123456789
01234567890123456789

Sample Output 2

20

Note that he must stop all the reels and make them display the same character.

Sample Input 3

5
11111
22222
33333

Sample Output 3

-1

It is impossible to stop the reels so that all the displayed characters are the same.
In this case, 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

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, \ldots, vertex N, and the i-th (1\leq i\leq M) edge connects vertices U_i and V_i.

Find the lexicographically smallest simple path from vertex X to vertex Y in G.
That is, find the lexicographically smallest among the integer sequences P=(P_1,P_2,\ldots,P_{\lvert P\rvert}) that satisfy the following conditions:

• 1\leq P_i\leq N
• If i\neq j, then P_i\neq P_j.
• P_1=X and P_{\lvert P\rvert}=Y.
• For 1\leq i\leq \lvert P\rvert-1, there exists an edge connecting vertices P_i and P_{i+1}.

One can prove that such a path always exists under the constraints of this problem.

You are given T test cases, so find the answer for each.

Constraints

• 1\leq T\leq 500
• 2\leq N\leq 1000
• N-1\leq M\leq \min\left( \frac{N(N-1)}{2},5\times 10^4\right)
• 1\leq X,Y \leq N
• X\neq Y
• 1\leq U_i<V_i \leq N
• If i\neq j, then (U_i,V_i)\neq (U_j,V_j).
• The given graph is connected.
• The sum of N over all test cases in each input is at most 1000.
• The sum of M over all test cases in each input is at most 5\times 10^4.
• All input values are integers.

Sample Input 1

2
6 10 3 5
1 2
1 3
1 5
1 6
2 4
2 5
2 6
3 4
3 5
5 6
3 2 3 2
1 3
2 3

Sample Output 1

3 1 2 5
3 2

For the first test case, graph G is as follows:

The simple paths from vertex 3 to vertex 5 on G, listed in lexicographic order, are as follows:

• (3,1,2,5)
• (3,1,2,6,5)
• (3,1,5)
• (3,1,6,2,5)
• (3,1,6,5)
• (3,4,2,1,5)
• (3,4,2,1,6,5)
• (3,4,2,5)
• (3,4,2,6,1,5)
• (3,4,2,6,5)
• (3,5)

Among these, the lexicographically smallest is (3,1,2,5), so output 3,1,2,5 separated by spaces on the first line.

For the second test case, (3,2) is the only simple path from vertex 3 to vertex 2.

Problem Statement

There are N push buttons. One of them is the winning button, and the other N-1 are losing buttons.

Aoki knows which button is winning, but Takahashi does not. Also, Takahashi cannot distinguish the N buttons.

They play a game using these buttons. The game consists of repeating the following sequence T times:

1. Aoki arranges the N buttons in a random order.
2. Takahashi performs the operation “choose a button and press it” M times. He may choose the same button multiple times.
3. Aoki tells Takahashi the number of times the winning button has been pressed so far since the start of the game.

Takahashi wins if and only if the winning button has been pressed a total of at least K times throughout the T repetitions.

Find Takahashi’s probability of winning when he plays to maximize his win probability.

Constraints

• 1 \le N \le 2\times 10^5
• 1 \le T \le 30
• 1 \le M \le 30
• 1 \le K \le 30
• All input values are integers.

Sample Input 1

3 2 2 3

Sample Output 1

0.222222222222222

The game can proceed as follows (not necessarily optimally):

• 1st repetition
  • Aoki randomly arranges the buttons so that the winning button is at position 1, and the losing buttons are at positions 2 and 3.
  • Takahashi presses button 1.
  • Takahashi presses button 2.
  • Aoki tells him the winning button has been pressed 1 time.
• 2nd repetition
  • Aoki randomly arranges the buttons so that the winning button is at position 3, and the losing buttons are at positions 1 and 2.
  • Takahashi presses button 3.
  • Takahashi presses button 3.
  • Aoki tells him the winning button has been pressed 3 times.
• Since the winning button has been pressed not less than 3 times, Takahashi wins.

The true answer in this case is \tfrac{2}{9}, so outputs like 0.222222 or 0.222223141592 are also accepted.

Sample Input 2

10 1 10 1

Sample Output 2

1.000000000000000

Sample Input 3

100 10 10 2

Sample Output 3

0.401263060761621