Problem Statement

There are N oranges. He repeats eating one orange as long as there is at least one, but he will be satisfied and stop eating after eating three. How many oranges will be left?

Constraints

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

Sample Input 1

5

Sample Output 1

2

He will be satisfied after eating three oranges, so two oranges will be left.

Sample Input 2

2

Sample Output 2

0

He eats up all the oranges before being satisfied, so no oranges will be left.

Problem Statement

The children on a southern island all hate school. In bad weather, they do not hesitate to be late for or absent from school. Specifically,

• They will be absent from school if it is rainy.
• They will be late for school if it is not rainy but windy.
• They will attend school without being late if it is not rainy nor windy.

Today's weather is described by two integers W and R. It is windy today if W=1 and it is not if W=0; likewise, it is rainy today if R=1 and it is not if R=0.

Print attend if the children on the island will attend school without being late, late if they will be late, and absent if they will be absent today.

Constraints

• Each of W and R is 0 or 1.

Sample Input 1

0 1

Sample Output 1

absent

It is rainy today, so they will be absent from school.

Sample Input 2

1 0

Sample Output 2

late

It is not rainy but windy today, so they will be late for school.

Sample Input 3

0 0

Sample Output 3

attend

It is not rainy nor windy today, so they will attend school without being late.

Problem Statement

Given a string S consisting of lowercase English letters, make all the vowels uppercase and print the result. Here, vowels consist of five letters: a, e, i, o, and u.

Constraints

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

Sample Input 1

atcoder

Sample Output 1

AtcOdEr

atcoder contains three vowels a, o, and e. Make them uppercase to obtain AtcOdEr and print it.

Sample Input 2

rhythm

Sample Output 2

rhythm

Note that y is not a vowel in this problem.

Sample Input 3

wow

Sample Output 3

wOw

Note that w is not a vowel in this problem.

Problem Statement

You are given N cards with strings written on them. The i-th card has a string S_i written on it (1\leq i\leq N).

Determine if one can choose three distinct cards from the N cards so that:

• the concatenation of the strings on two of the cards in any order coincides with the string written on the other.

Constraints

• 3\leq N\leq 10
• N is an integer.
• S_i is a string of lowercase English letters of length between 1 and 10, inclusive.
• S_i\neq S_j(i\neq j)

Sample Input 1

4
ing
string
abc
str

Sample Output 1

Yes

Choosing the 1-st, 2-nd, and 4-th cards is valid because the concatenation of the strings written on the 4-th and 1-st in this order coincides with the string written on the 2-nd.

Sample Input 2

3
abc
def
abcabc

Sample Output 2

No

The chosen cards must be pairwise distinct.

Sample Input 3

6
vxyzbkfvmb
wjrbbfogg
jmeedirhy
bkfvmb
vxyz
acheswkrui

Sample Output 3

Yes

Problem Statement

There is a piano with N keys. Key i plays an A_i-hertz tone.
The keys are in ascending order; that is, A_1 < A_2 < \dots < A_N.

You want to play a song with this piano using only your right index finger.
The song is a sequence of M tones, each of B_1,B_2,\dots, and B_M hertz, in this order.

Pressing key j after key i requires moving the finger by the distance |i-j|. Find the total distance required for the finger to move since playing the first tone until playing the last.

Constraints

• 1 \leq N \leq 3\times 10^5
• 1 \leq M \leq 3\times 10^5
• 1 \leq A_i,B_i \leq 10^9
• The keys are in ascending order; that is, A_1 < A_2 < \dots < A_N.
• The song can be played by the piano; in other words, for every i there exists k such that A_k=B_i.
• All input values are integers.

Sample Input 1

8 7
262 294 330 349 392 440 494 523
262 262 392 392 440 440 392

Sample Output 1

6

You need to press keys 1,1,5,5,6,6, and 5 to play the tones, so the finger's traveling distances are 0,4,0,1,0, and 1 in order, for a total of 6.

Sample Input 2

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

Sample Output 2

92

Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\ldots,A_N) and a length-M integer sequence B=(B_1,B_2,\ldots,B_M).

Determine if A is a subsequence of B. In other words, determine if one can remove zero or more elements of B and concatenate the remaining elements without changing the order to make B coincide with A.

Constraints

• 1\le N\le M\le 2\times 10^5
• 1\le A_i,B_i\le 10^9
• All input values are integers.

Sample Input 1

3 5
3 1 4
3 6 1 1 4

Sample Output 1

Yes

Removing B_2 and B_4 from B yields (3,1,4), which coincides with A. Thus, A turns out to be a subsequence of B, so print Yes.

Sample Input 2

2 3
5 4
4 7 5

Sample Output 2

No

Removing any element from B does not yield A, so print No.

Sample Input 3

3 3
7 7 7
7 7 7

Sample Output 3

Yes

The answer is Yes even if A and B are originally equal.

Sample Input 4

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

Sample Output 4

Yes

Problem Statement

You are playing a video game.

In this game, raising a character from level x to level (x+1) requires consuming (Ax+B) gems.

If you have N gems, to what level can you raise a level-0 character?

Answer Q test cases.

Constraints

• 1 \leq Q \leq 10^5
• 1 \leq A,B \leq 10^9
• 0 \leq N \leq 10^{18}
• All input values are integers.

Sample Input 1

3
10 2 3
1000000000000000000 1 1
0 1000000000 1000000000

Sample Output 1

2
1414213561
0

For the first test case, the number of gems required to raise the level is as follows:

• 3 gems to raise it from level 0 to level 1.
• 5 gems to raise it from level 1 to level 2.
• 7 gems to raise it from level 2 to level 3.

If you have 10 gems, you can raise a level-0 character up to level 2.

Problem Statement

N bus stops are arranged from left to right, numbered 1,2,\ldots,N in order.

There are M bus routes. Route i (1 \leq i \leq M) operates bidirectionally between bus stops L_i and R_i, stopping at every bus stop in between, including these two.

Find how many routes stop at each bus stop.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq M \leq 3 \times 10^5
• 1 \leq L_i,R_i \leq N (1 \leq i \leq M)
• L_i \neq R_i (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

2 4 4 3 2

Route 1 stops at bus stops 1,2,3; route 2 at 2,3,4,5; route 3 at 1,2,3,4; route 4 at 2,3; and route 5 at 4,5.

In other words, routes 1 and 3 stop at bus stop 1; routes 1,2,3,4 stop at 2; routes 1,2,3,4 stop at 3; route 2,3,5 stop at 4; and routes 2,5 stop at 5.

Thus, the numbers to be printed are 2,4,4,3,2, in order.

Sample Input 2

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

Sample Output 2

2 5 4 4 4 4 6 4 2 0

Problem Statement

There is a grid with 10^9 cells on each side, and all the cells are initially white. The cell in the i-th row from the top and j-th column from the left is called (i,j).
We will perform N operations. The i-th operation is as follows:

• Paint cells in an X shape centered at (P_i,Q_i). More formally, paint the following cells black for all integers k:
  • Paint (P_i+k,Q_i+k) black if 1 \le P_i+k \le 10^9 and 1 \le Q_i+k \le 10^9.
  • Paint (P_i+k,Q_i-k) black if 1 \le P_i+k \le 10^9 and 1 \le Q_i-k \le 10^9.

Print the subrectangle in the A-th through B-th rows form the top and the C-th through D-th columns from the left in the resulting grid.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le P_i, Q_i \le 10^9
• 1 \le A \le B \le 10^9
• 1 \le C \le D \le 10^9
• (B-A+1) \times (D-C+1) \le 2 \times 10^5

Sample Input 1

3 2 6 3 9
3 5
5 1
4 9

Sample Output 1

.#.##..
#.#..#.
.#.#..#
#...##.
....##.

The top-left cells initially look like this:

..........
..........
..........
..........
..........
..........
..........

The first operation paints cells in an X shape centered at (3,5), resulting in the following:

..#...#...
...#.#....
....#.....
...#.#....
..#...#...
.#.....#..
#.......#.

The second operation paints cells in an X shape centered at (5,1), resulting in the following:

..#.#.#...
...#.#....
..#.#.....
.#.#.#....
#.#...#...
.#.....#..
#.#.....#.

The third operation paints cells in an X shape centered at (4,9), resulting in the following:

..#.###...
...#.##...
..#.#..#.#
.#.#.#..#.
#.#...##.#
.#....##..
#.#..#..#.

Print the cells in the 2-th through 6-th rows form the top and the 3-th through 9-th columns from the left, as shown below:

.#.##..
#.#..#.
.#.#..#
#...##.
....##.

Problem Statement

There is an N-vertex tree T. Edge i (1\le i\le N - 1) connects vertices u_i and v_i and has a weight w_i.

For an integer pair (i,j) with 1\le i < j\le N, let f(i,j) be the total XOR of the weights of the edges contained in the simple path from vertex i to vertex j of the tree T.

Find the total XOR of f(i,j) over all integer pairs (i,j) with 1\le i < j\le N.

Constraints

• 2\le N\le 2\times 10^5
• 1\le u_i < v_i\le N
• 0\le w_i< 2^{30}
• The given graph is a tree.
• All input values are integers.

Sample Input 1

3
2 3 4
1 2 3

Sample Output 1

0

For example, the weights of the edges contained in the simple path from vertex 1 to vertex 3 are 3 and 4, so f(1,3) is the XOR of 3 and 4, which is 7.

We can also find f(1,2)=3 and f(2,3)=4, so the answer is the total XOR of 7,3, and 4, which is 0.

Sample Input 2

4
1 4 8
1 2 2
1 3 5

Sample Output 2

15

Sample Input 3

6
3 5 3
4 5 11
1 6 7
2 3 1
1 3 4

Sample Output 3

13

Problem Statement

You are given a positive integer N and a permutation A=(A_1,A_2,\dots,A_N) of (1,2,\dots,N). Find the following value for each i=1,2,\dots,N:

• the maximum integer j such that 1 \leq j < i and A_j > A_i if such an integer exists, or -1 otherwise.

Constraints

• 1 \leq N \leq 5 \times 10^5
• A is a permutation of (1,2,\dots,N).

Sample Input 1

4
3 1 4 2

Sample Output 1

-1 1 -1 3

• i=1: No j satisfies the condition, so the answer is -1.
• i=2: j=1 satisfies the condition, so the answer is 1.
• i=3: No j satisfies the condition, so the answer is -1.
• i=4: j=1,3 satisfy the condition, so the answer is 3, the larger of them.

Sample Input 2

7
3 7 2 1 6 5 4

Sample Output 2

-1 -1 2 3 2 5 6

Problem Statement

There are N people numbered 1 through N. The strength of each person is represented by an integer between 1 and N, and all strengths are distinct.

If two people battles, the one with the larger strength always wins.

You are given preliminary results of a round-robin competition between the N people. They are represented by N strings S_1,S_2,\ldots, and S_N and satisfy the following conditions:

• If the j-th character of S_i is o: person i has battled person j and won.
• If the j-th character of S_i is x: person i has battled person j and lost.
• If the j-th character of S_i is ?: person i has not battled person j yet.
• If the j-th character of S_i is -: it holds that i=j.

Fill each ? in S_1,S_2,\ldots, and S_N with o or x consistently. If any assignment causes a contradiction, report that fact.

More precisely, determine if one can replace each occurrence of ? in S_1,S_2,\ldots, and S_N with either o or x subject to the following condition, and print one such assignment if it is possible.

• There exists a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) such that:
  • for every integer pair (i,j) with i\neq j, the j-th character of S_i is o if P_i>P_j and x if P_i<P_j.

Constraints

• 1\le N\le 10^3
• N is an integer.
• Each of S_1,S_2,\ldots, and S_N is a string of length N consisting of o, x, ?, and -.
• If the j-th character of S_i is o, then the i-th character of j is x.
• If the j-th character of S_i is x, then the i-th character of j is o.
• The i-th character of S_i is -.
• If i\neq j, then the j-th character of S_i is not -.

Sample Input 1

4
-?x?
?-o?
ox-?
???-

Sample Output 1

Yes
-xxx
o-oo
ox-o
oxx-

For example, it is consistent with the preliminary results to assume that the strengths of people 1,2,3, and 4 are 1,4,3, and 2, respectively.

Another possible assignment is:

Yes
-xxx
o-ox
ox-x
ooo-

Sample Input 2

4
-oxo
x-xx
oo-o
xox-

Sample Output 2

Yes
-oxo
x-xx
oo-o
xox-

There may be no ?.

Sample Input 3

3
-ox
x-o
ox-

Sample Output 3

No

Any assignment of strengths of people 1,2, and 3 is inconsistent with the preliminary results.

Sample Input 4

6
-x?x??
o-o??o
?x-???
o??-o?
???x-o
?x??x-

Sample Output 4

Yes
-xxxxx
o-oxxo
ox-xxx
ooo-oo
ooox-o
oxoxx-

Problem Statement

You are given two sequences A=(A_1,\ldots,A_N) and B=(B_1,\ldots,B_N) of length N.

Define a sequence C as the one obtained by starting with an empty sequence and appending A_i copies of B_i, resulting in a length of \sum_{i=1}^N A_i.

Find the inversion number of C.

Constraints

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

Sample Input 1

3
4 1 2
10 30 20

Sample Output 1

2

The sequence C is (10,10,10,10,30,20,20), whose inversion number is 2.

Sample Input 2

4
1000 1000 1000 1000
1 1 1 1

Sample Output 2

0

The inversion number of C is 0.

Sample Input 3

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

Sample Output 3

499

Problem Statement

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

Find the minimum length of a string consisting of lowercase English letters that contains S as a substring at least K times.

Here, a substring refers to a (consecutive) subarray. For example, xxx is a substring of yxxxy, but not of xxyxx.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq K \leq 10^9
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

7 2
strings

Sample Output 1

13

The string stringstrings of length 13 contains strings as a substring twice. No string of length 12 or less satisfies the condition, so the answer is 13.

Sample Input 2

5 30
abcab

Sample Output 2

92

Problem Statement

You are given two sequences A=(A_1,\ldots,A_N) and B=(B_1,\ldots,B_N) of length N.

Process the given Q queries in order. Each query is of one of the following kinds:

• 1 p x: set A_p to x.
• 2 p x: set B_p to x.
• 3 l r x: determine if there exists an integer pair (i,j) such that l\leq i\leq j\leq r and A_i+A_{i+1}+\dots+A_j\equiv x \pmod 3. If it exists, print the maximum value of B_i+B_{i+1}+\dots+B_j among such (i,j).

Constraints

• 1\leq N,Q \leq 2\times 10^5
• 0\leq A_i \leq 2
• -10^9\leq B_i \leq 10^9
• For every query of the first kind:
  • 1\leq p \leq N
  • 0\leq x \leq 2
• For every query of the second kind:
  • 1\leq p \leq N
  • -10^9\leq x \leq 10^9
• For every query of the third kind:
  • 1\leq l\leq r \leq N
  • 0\leq x \leq 2
• All input values are integers.

Sample Input 1

3 5
0 1 2
3 12 -5
3 1 3 0
1 3 0
3 2 3 1
2 3 2
3 2 3 1

Sample Output 1

10
12
14

• 1-st query: there are three integer pairs (i,j) such that 1\leq i\leq j\leq 3 and A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3: namely (1,1),(1,3), and (2,3). The values of B_i+B_{i+1}+\dots+B_j are 3,10, and 7, respectively, so print the maximum value 10 among them.
• 2-nd query: set A_3 to 0.
• 3-rd query: there are two integer pairs (i,j) such that 2\leq i\leq j\leq 3 and A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3: namely (2,2) and (2,3). The values of B_i+B_{i+1}+\dots+B_j are 12 and 7, respectively, so print the maximum value 12 among them.
• 4-th query: set B_3 to 2.
• 5-th query: there are two integer pairs (i,j) such that 2\leq i\leq j\leq 3 and A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3: namely (2,2) and (2,3). The values of B_i+B_{i+1}+\dots+B_j are 12 and 14, respectively, so print the maximum value 14 among them.

Sample Input 2

1 3
2
100
3 1 1 0
3 1 1 1
3 1 1 2

Sample Output 2

No
No
100

For the 1-st query, there is no integer pair (i,j) such that 1\leq i\leq j\leq 1 and A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3.

Sample Input 3

1 1
2
100
1 1 0

Sample Output 3

There may be no query of the third type.

Sample Input 4

10 10
1 1 2 0 0 2 0 2 0 0
-52 -52 14 -11 -2 -54 46 8 26 -17
3 1 9 2
2 8 71
1 10 1
2 9 86
1 5 2
3 7 7 0
3 4 5 0
2 10 100
2 1 -95
1 1 1

Sample Output 4

80
46
-11