Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

• abc is a 3-digit integer abc none of whose digits is 0.

Sample Input 1

123

Sample Output 1

666

We have 123+231+312=666.

Sample Input 2

999

Sample Output 2

2997

We have 999+999+999=2997.

Problem Statement

Takahashi has recorded the number of steps he walked for N weeks. He walked A_i steps on the i-th day.

Find the total number of steps Takahashi walked each week.
More precisely, find the sum of the steps for the first week (the 1-st through 7-th day), the sum of the steps for the second week (the 8-th through 14-th day), and so on.

Constraints

• 1 \leq N \leq 10
• 0 \leq A_i \leq 10^5
• All input values are integers.

Sample Input 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

Sample Output 1

28000 35000

For the first week, he walked 1000+2000+3000+4000+5000+6000+7000=28000 steps, and for the second week, he walked 2000+3000+4000+5000+6000+7000+8000=35000 steps.

Sample Input 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

Sample Output 2

314333 419427 335328

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

• if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
• if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

• if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
• if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

• N and K are integers.
• 1 \le K \le N \le 100
• S is a string of length N consisting of o and x.
• S has at least K o's.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

• The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
• The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
• The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
• The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
• The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
• Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

Problem Statement

In a certain measurement, the sensor readings at times 0,1,\dots,T are recorded according to the following rules.

• At time 0, the reading is saved.
• At times 1,2,\dots,T, the reading is saved if and only if the absolute difference between the current reading and the most recently saved reading is at least X.

The sensor reading at time i=0,1,\dots,T was A_i.

Output the times at which readings were saved and the saved values, in ascending order of time.

Constraints

• 1 \le T \le 100
• 1 \le X \le 100
• 0 \le A_i \le 100
• All input values are integers.

Sample Input 1

6 10
30 35 40 21 30 12 31

Sample Output 1

0 30
2 40
3 21
6 31

The measurement proceeds as follows.

• The reading at time 0 is 30. Save it.
• The reading at time 1 is 35. The most recently saved reading is 30, and the absolute difference is less than 10, so it is not saved.
• The reading at time 2 is 40. The most recently saved reading is 30, and the absolute difference is at least 10, so it is saved.
• The reading at time 3 is 21. The most recently saved reading is 40, and the absolute difference is at least 10, so it is saved.
• The reading at time 4 is 30. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
• The reading at time 5 is 12. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
• The reading at time 6 is 31. The most recently saved reading is 21, and the absolute difference is at least 10, so it is saved.

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq D\leq 2\times 10^5
• 1\leq P\leq 10^9
• 1\leq F_i\leq 10^9
• All input values are integers.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N versions of a certain OS, numbered 1,2,\dots,N in chronological order.
There are N PCs, and initially the OS version of the i-th PC is i.

Perform Q operations in order. The i-th operation is as follows:

• Upgrade all PCs whose current OS version is X_i or earlier to version Y_i(>X_i). Then, print the number of PCs upgraded in this operation.

Note that for i<Q, the upgrades from the i-th operation are performed before proceeding to the (i+1)-th operation.

Constraints

• All input values are integers.
• 2 \le N \le 10^6
• 1 \le Q \le 2 \times 10^5
• 1 \le X_i < Y_i \le N

Sample Input 1

8 5
2 6
3 5
1 7
5 7
7 8

Sample Output 1

2
1
0
3
7

This input contains five operations.

• Initially, the versions of the eight PCs are 1,2,3,4,5,6,7,8.
• In the first operation, PCs with version 2 or earlier are upgraded to version 6.
  • This operation upgrades two PCs, and the versions of the PCs become 6,6,3,4,5,6,7,8.
• In the second operation, PCs with version 3 or earlier are upgraded to version 5.
  • This operation upgrades one PC, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the third operation, PCs with version 1 or earlier are upgraded to version 7.
  • This operation upgrades zero PCs, and the versions of the PCs become 6,6,5,4,5,6,7,8.
• In the fourth operation, PCs with version 5 or earlier are upgraded to version 7.
  • This operation upgrades three PCs, and the versions of the PCs become 6,6,7,7,7,6,7,8.
• In the fifth operation, PCs with version 7 or earlier are upgraded to version 8.
  • This operation upgrades seven PCs, and the versions of the PCs become 8,8,8,8,8,8,8,8.

Problem Statement

There is a grid with N rows and N columns, where N is an odd number at most 45.

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

In this grid, you will place Takahashi and a dragon consisting of N^2-1 parts numbered 1 to N^2-1 in such a way that satisfies the following conditions:

• Takahashi must be placed at the center of the grid, that is, in cell (\frac{N+1}{2},\frac{N+1}{2}).
• Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
• For every integer x satisfying 2 \leq x \leq N^2-1, the dragon part x must be placed in a cell adjacent by an edge to the cell containing part x-1.
  • Cells (i,j) and (k,l) are said to be adjacent by an edge if and only if |i-k|+|j-l|=1.

Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.

Constraints

• 3 \leq N \leq 45
• N is odd.

Sample Input 1

5

Sample Output 1

1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9

The following output also satisfies all the conditions and is correct.

9 10 11 14 15
8 7 12 13 16
5 6 T 18 17
4 3 24 19 20 
1 2 23 22 21

On the other hand, the following outputs are incorrect for the reasons given.

Takahashi is not at the center.

1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 T

The cells containing parts 23 and 24 are not adjacent by an edge.

1 2 3 4 5
10 9 8 7 6
11 12 24 22 23
14 13 T 21 20
15 16 17 18 19

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Find the value of the following expression:

Constraints

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

Sample Input 1

3
1 3 2

Sample Output 1

3

A_1 \oplus A_2 = 2, A_1 \oplus A_2 \oplus A_3 = 0, and A_2 \oplus A_3 = 1, so the answer is 2 + 0 + 1 = 3.

Sample Input 2

7
2 5 6 5 2 1 7

Sample Output 2

83

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N).
Calculate the following expression:

The constraints guarantee that the answer is less than 2^{63}.

Constraints

• 2 \leq N \leq 4 \times 10^5
• 0 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

3
2 5 3

Sample Output 1

4

For (i, j) = (1, 2), we have \max(A_j - A_i, 0) = \max(3, 0) = 3.
For (i, j) = (1, 3), we have \max(A_j - A_i, 0) = \max(1, 0) = 1.
For (i, j) = (2, 3), we have \max(A_j - A_i, 0) = \max(-2, 0) = 0.
Adding these together gives 3 + 1 + 0 = 4, which is the answer.

Sample Input 2

10
5 9 3 0 4 8 7 5 4 0

Sample Output 2

58