Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

• S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Sample Input 1

tourist

Sample Output 1

3858

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is 3481.

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

• N is an odd number between 1 and 99, inclusive.
• S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

• 2 \leq N \leq 100
• A_{i,j} \in \lbrace 0,1 \rbrace
• A_{i,i} = 0
• A_{i,j} = A_{j,i}
• All input values are integers.

Sample Input 1

4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

Sample Output 1

2 3
1 4
1
2

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

5
0 1 0 1 1
1 0 0 1 0
0 0 0 0 1
1 1 0 0 1
1 0 1 1 0

Sample Output 3

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

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

• 1 x: Append x to the end of A.
• 2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

• 1 \leq Q \leq 100
• In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
• In the second type of query, k is a positive integer not greater than the current length of sequence A.

Sample Input 1

5
1 20
1 30
2 1
1 40
2 3

Sample Output 1

30
20

• Initially, A is empty.
• The first query appends 20 to the end of A, making A=(20).
• The second query appends 30 to the end of A, making A=(20,30).
• The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
• The fourth query appends 40 to the end of A, making A=(20,30,40).
• The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

15

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

31

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• The playlist does not change songs at exactly T seconds after it starts playing.
• All values in the input are integers.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

• From time 0 to time 180, song 1 plays.
• From time 180 to time 420, song 2 plays.
• From time 420 to time 540, song 3 plays.
• From time 540 to time 720, song 1 plays.
• From time 720 to time 960, song 2 plays.
• \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.

Given Q queries, process all of them in order. The q-th (1\leq q\leq Q) query is in one of the following three formats, which represents the following queries:

• 1\ x _ q: assign x_q to every element of A.
• 2\ i _ q\ x _ q: add x_q to A _ {i _ q}.
• 3\ i _ q: print the value of A _ {i _ q}.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq Q \leq 2\times10^5
• 0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
• If the q-th (1\leq q\leq Q) query is in the second or third format, 1 \leq i _ q \leq N.
• If the q-th (1\leq q\leq Q) query is in the first or second format, 0 \leq x _ q \leq 10^9.
• There exists a query in the third format.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
8
5

Initially, A=(3,1,4,1,5). The queries are processed as follows:

• A_2=1, so print 1.
• Add 4 to A_3, making A=(3,1,8,1,5).
• A_3=8, so print 8.
• Assign 1 to every element of A, making A=(1,1,1,1,1).
• Add 4 to A_3, making A=(1,1,5,1,1).
• A_3=5, so print 5.

Sample Input 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

Sample Output 2

8000000000

Note that the elements of A may not fit into a 32-bit integer type.

Sample Input 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

Sample Output 3

7
5
7
21
21
19
10

Problem Statement

There are N baskets numbered 1, 2, \ldots, N arranged in a circle.
For each 1\leq i \leq N-1, basket i+1 is to the immediate right of basket i, and basket 1 is to the immediate right of basket N.

Basket i now contains A_i apples.

Takahashi starts in front of basket 1 and repeats the following action.

• If the basket he is facing contains an apple, take one and eat it. Then, regardless of whether he has eaten an apple now, go on to the next basket to the immediate right.

Find the number of apples remaining in each basket when Takahashi has eaten exactly K apples in total.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{12}
• 1 \leq K \leq 10^{12}
• There are at least K apples in total. That is, \sum_{i=1}^{N}A_i\geq K.
• All values in the input are integers.

Sample Input 1

3 3
1 3 0

Sample Output 1

0 1 0 

Takahashi will do the following.

• Basket 1, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 2. Now, the baskets have 0,3,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,2,0 apples.
• Basket 3, which he is facing, contains no apple. Then, he goes on to basket 1. Now, the baskets have 0,2,0 apples.
• Basket 1, which he is facing, contains no apple. Then, he goes on to basket 2. Now, the baskets have 0,2,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,1,0 apple(s).

Sample Input 2

2 1000000000000
1000000000000 1000000000000

Sample Output 2

500000000000 500000000000 

Problem Statement

The shop supaisu-ya sells 2^N-1 kinds of spices: Spice 1, Spice 2, \ldots, Spice 2^N-1. One pack of each spice is in stock. For each i = 1, 2, \ldots, 2^N-1, Spice i costs c_i yen. Takahashi can buy any of these spices.

He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If k spices, Spice A_1, Spice A_2, \ldots, Spice A_k, are mixed, the hotness of the resulting curry is A_1 \oplus A_2 \oplus \cdots \oplus A_k, where \oplus denotes the bitwise XOR.

Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from 1 through 2^N-1. Print the minimum possible amount of money Takahashi pays.

Constraints

• 2 \leq N \leq 16
• 1 \leq c_i \leq 10^9
• All values in input are integers.

Sample Input 1

2
4 5 3

Sample Output 1

7

If Takahashi buys Spice 1 and 3, he can make curry of any hotness from 1 through 3, as follows.

• To make curry of hotness 1, use just Spice 1.
• To make curry of hotness 2, mix Spice 1 and Spice 3.
• To make curry of hotness 3, use just Spice 3.

Here, Takahashi pays c_1 + c_3 = 4 + 3 = 7 yen, which is the minimum possible amount he pays.

Sample Input 2

4
9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

Sample Output 2

15