Problem Statement

You are going to throw away a rectangular cuboid of depth X centimeters, width Y centimeters, and height Z centimeters.

An item is regarded as bulky trash if its depth, width, or height is at least S centimeters. Is the item you are discarding bulky trash?

Constraints

• 1\leq X,Y,Z,S \leq 1000
• All input values are integers.

Sample Input 1

10 20 30 100

Sample Output 1

No

Its depth, width, and height are all strictly less than 100 centimeters, so it is not bulky trash.

Sample Input 2

50 100 150 130

Sample Output 2

Yes

Its height is not less than 130 centimeters, so it is bulky trash.

Sample Input 3

50 50 50 50

Sample Output 3

Yes

Problem Statement

On AtCoder, the competitive programming website, each user is graded by a value called rating. Every time a user participates in a programming contest, their performance is quantified and affects their rating.

If a user's rating before a contest is R and their performance in the contest is P, their rating after the contest R' is approximated by:

R' = \lfloor 0.9 \times R + 0.1 \times P \rfloor,

where \lfloor x \rfloor represents the maximum integer not exceeding x.

Given R and P as input, evaluate and print R' according to the approximation formula above.

Constraints

• 1 \leq R, P \leq 4400
• R and P are integers.

Sample Input 1

2516 2320

Sample Output 1

2496

We have R' = \lfloor 0.9 \times 2516 + 0.1 \times 2320 \rfloor = \lfloor 2496.4 \rfloor = 2496.

Sample Input 2

2498 3200

Sample Output 2

2568

Sample Input 3

1 1

Sample Output 3

1

Problem Statement

There are two traffic lights, light 1 and light 2. Light i (i=1,2) repeatedly shows green light for B_i seconds and red light for R_i seconds.
In other words, if light i turns from red to green at some point, it remains green for the next B_i seconds, and then remains red for the succeeding R_i seconds; this way, it alternates between green and red light indefinitely.

Now, the two lights have simultaneously turned from red to green.
Within the next T seconds, how many seconds do both light 1 and light 2 show green?

Constraints

• 1\leq B_i,R_i\leq 100
• 1\leq T\leq 10^4
• All input values are integers.

Sample Input 1

2 3 5 1 10

Sample Output 1

3

Within the 10 seconds right after the two traffic lights simultaneously turn from red to green, the lights transition as follows:

• From 0 to 2 seconds after the switch, both light 1 and light 2 are green.
• From 2 to 5 seconds after the switch, light 1 is red and light 2 is green.
• From 5 to 6 seconds after the switch, light 1 is green and light 2 is red.
• From 6 to 7 seconds after the switch, both light 1 and light 2 are green.
• From 7 to 10 seconds after the switch, light 1 is red and light 2 is green.

Therefore, both lights show green from 0 to 2 and from 6 to 7 seconds after the switch, for a total of 3 seconds.

Sample Input 2

100 100 100 100 10000

Sample Output 2

5000

Both lights show green for 100 seconds, followed by red for 100 seconds; this sequence repeats indefinitely.

Problem Statement

N players numbered 1 through N are playing a multiplayer fighting game. When a match starts, the N players enter a ring at once. Initially, each player's score is 0.

Then, M events occur during the match. Each event is of type 1 or type 2 described below:

• Type 1: represented in the following format. Player x attacks player y.

1 x y

• Type 2: represented in the following format. Player z drops out of the ring.

2 z

When a player drops out of the ring, the following events immediately occur:

• The score of the player who has dropped out decreases by 1.
• If the player who has dropped out was attacked at least once since the last entrance, the score of the player who made the last such attack increases by 1.
• Then, the player enters the ring again.

Print the final score of each player.

Constraints

• All input values are integers.
• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq x, y, z \leq N
• x \neq y

Sample Input 1

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

Sample Output 1

0 -1 -2 1

When the match starts, 4 players enter the ring, and the players' scores are (S_1, S_2, S_3, S_4) = (0, 0, 0, 0). Then, the following events occur during the match:

• In the 1-st event, player 2 attacks player 3.
• In the 2-nd event, player 4 attacks player 3.
• In the 3-rd event, player 3 drops out, so their score decreases by 1. Since player 3's last entrance (i.e. since the match begins), they are attacked in the 1-st and 2-nd event. The last one among them is made by player 4, so their score increases by 1. Subsequently, player 3 enters the ring again.
• In the 4-th event, player 2 attacks player 1.
• In the 5-th event, player 2 drops out, so their score decreases by 1. Since player 2's last entrance (i.e. since the match begins), they are never attacked. Subsequently, player 2 enters the ring again.
• In the 6-th event, player 3 drops out, so their score decreases by 1. Since player 3's last entrance (i.e. since the 3-rd event), they are never attacked. Subsequently, player 3 enters the ring again.

The final scores of the players are (S_1, S_2, S_3, S_4) = (0, -1, -2, 1).

Sample Input 2

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

Sample Output 2

-1 -1 -1 0 0

Problem Statement

There are N sets of integers: S_1, S_2, \dots, S_N.
S_i contains C_i integers, A_{i, 1}, \dots, A_{i, C_i}, in ascending order.
Among the ways to choose two or more of the sets, how many of them satisfy the following condition?

• The intersection of the chosen sets contains only odd numbers.

Here, the intersection of chosen sets is the set consisting of the integers contained in all of the chosen sets.

Constraints

• 2 \leq N \leq 10
• 1 \leq C_i \leq 10
• 1 \leq A_{i,1} \lt A_{i,2} \lt \dots \lt A_{i,C_i} \leq 100
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

We enumerate the possible choices of sets, their intersections, and whether they satisfy the condition:

• The intersection of S_1 and S_2 is \lbrace 1, 5 \rbrace, which satisfies the condition.
• The intersection of S_1 and S_3 is \lbrace 2 \rbrace, which does not satisfy the condition.
• The intersection of S_2 and S_3 is \lbrace 3 \rbrace, which satisfies the condition.
• The intersection of S_1, S_2, and S_3 is \lbrace \rbrace (an empty set), which satisfies the condition.

Note that the condition is satisfied even when the intersection is an empty set.

Sample Input 2

5
6 4 5 6 9 10 17
5 1 7 9 13 20
6 2 5 8 15 16 20
6 2 5 6 7 16 19
1 3

Sample Output 2

23

Problem Statement

You are given an expression S consisting of one-letter variables, one-digit integers, and + and - signs.
For example, 1+2+3, 3-a+2+c+0, and 1 can be given,
but 12+3, 4-ab, and a/2+5 cannot, because 12 is not a one-digit integer, ab is not a one-letter variable (nor is it interpreted as a\times b), and it contains /, respectively.

You are given the values of the variables as N pairs, (c _ 1,v _ 1),(c _ 2,v _ 2),\ldots, and (c _ N,v _ N). The i-th pair (c _ i,v _ i) means that the variable c _ i should evaluate to the value v _ i.

Evaluate the expression S.

Constraints

• S is a string of length between 1 and 99, inclusive.
• S has an odd length.
• Each character at an odd-numbered position of S is a lowercase English letter or a digit.
• Each character at an even-numbered position of S is + or -.
• 1\leq N\leq 26
• c_i is a lowercase English letter (1\leq i\leq N).
• i\neq j\implies c _ i\neq c _ j\ (1\leq i,j\leq N)
• If a lowercase English letter c occurs in S, then there exists i\ (1\leq i\leq N) such that c=c _ i.
• -100\leq v _ i\leq100\ (1\leq i\leq N)
• N, v _ 1,v _ 2,\ldots, and v _ N are all integers.

Sample Input 1

2+a-7
1
a 18

Sample Output 1

13

When a=18, we have 2+a-7=2+18-7=13. Thus, 13 should be printed.

Sample Input 2

1
4
s 29
b -1
m -8
f -2

Sample Output 2

1

S may not contain a variable. Also, a value may be given for a variable that is not contained in S.

Sample Input 3

0-1+8-i+m-d-3-a-m+4+a+m-2+5+5-5
10
a 68
b -88
d -10
e -19
i -33
l -44
m -39
n 50
r -36
y 63

Sample Output 3

15

Problem Statement

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

You will apply the following operation against the sequence A exactly twice.

• Choose an integer i with 1 \leq i < N, and swap the values of A_i and A_{i + 1}.

Determine if you can make A = B by operating exactly twice.

Constraints

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

Sample Input 1

5
1 3 5 5 2
3 1 5 2 5

Sample Output 1

Yes

You can make A = B by operating exactly twice as follows:

• Choose i = 1. Swap the values of A_1 and A_2 to make A = (3, 1, 5, 5, 2).
• Choose i = 4. Swap the values of A_4 and A_5 to make A = (3, 1, 5, 2, 5).

Sample Input 2

3
2 2 2
3 3 3

Sample Output 2

No

Problem Statement

An object on a grid like these is called a C.

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

Illustrated above are Cs of level 1, 2, and 3, from left to right.

Formally, for a positive integer l, a C* of level l is defined as follows.

• A C of level l is an (l+2) \times (l+2) square grid.
• Every cell on the upper, left, or lower border of the square has # written on it.
• Every other cell has . written on it.

You are given an N \times N grid. Each cell has # or . written on it.
The grid is described by N strings S_1,S_2,\dots,S_N; the j-th character of S_i represents the character written on the cell in the i-th row from the top and j-th column from the left.

Find the maximum level of a C that can be obtained by extracting a (connected) square from this grid.
If no square extracted from the grid forms a C, print 0.

Constraints

• N is an integer between 3 and 300, inclusive.
• S_i is a length-N string consisting of # and ..

Sample Input 1

4
####
.#..
.###
#..#

Sample Output 1

1

If you extract the square consisting of 1-st through 3-rd rows from the top and 2-nd through 4-th columns, it forms a C of level 1.
One cannot extract a C of level 2 or greater from this grid.

Sample Input 2

5
.####
.###.
####.
##..#
###.#

Sample Output 2

0

One cannot extract a C from this grid.

Sample Input 3

10
.###...###
.#.....#..
.#########
...#......
...#......
...#......
##########
#.....#...
#.....#...
####..####

Sample Output 3

3

Problem Statement

There is a text editor that can be regarded as a grid extending infinitely toward right and downward. The cell in the i-th row from the top and j-th column from the left of the editor is denoted by (i, j). Each cell can have a character written on it, or be empty; initially, all cells are empty.
The editor also has a marker called a cursor, which indicates the position where a character is inserted. The cursor is initially located at (1, 1).

You are to process Q queries in given order.
Each query is one of the following three types.

• 1 c: Insert the character c at the current position of the cursor. Formally, perform the following procedure.
  • First, move all characters in the current cell of the cursor or in any cell to the right within the same row, one cell to the right, if any.
  • Next, write the character c onto the cell where the cursor is currently located at.
  • Finally, move the cursor one cell to the right.
• 2: Move the cursor to the leftmost cell of the current row.
• 3: Move the cursor to the leftmost cell of the row right below the current row.

Print the state of the editor after processing all the queries.

Constraints

• 1 \leq Q \leq 1.5 \times 10^6
• c is a lowercase English character.

Sample Input 1

8
1 b
1 c
1 d
2
1 a
3
3
1 e

Sample Output 1

3 2
# abcd
# 
# e

The query is processed as follows.

• In the 1-st query, write b onto (1, 1), and move the cursor to (1, 2).
• In the 2-nd query, write c onto (1, 2), and move the cursor to (1, 3).
• In the 3-rd query, write d onto (1, 3), and move the cursor to (1, 4).
• In the 4-th query, move the cursor to (1, 1).
• In the 5-th query, simultaneously move the following characters one cell to the right: b written on (1, 1), c written on (1, 2), and d written on (1, 3). Then, write a onto (1, 1), and move the cursor to (1, 2).
• In the 6-th query, move the cursor to (2, 1).
• In the 7-th query, move the cursor to (3, 1).
• In the 8-th query, write e onto (3, 1), and move the cursor to (3, 2).

Problem Statement

There is a grid with H horizontal rows and W vertical columns. The cell in the i-th row from the top and j-th column from the left is denoted by cell (i, j).
Initially, cell (i, j) is white if S_{i,j} is ., and black if it is #.

You are initially at cell (1,1). You can move to an adjacent cell in one of the four directions: up, down, left, and right. You cannot exit the grid.
Whenever you make a move, the color of the cell you step into flips (from white to black and vice versa).

Your objective is to make all the cells white. Find the minimum number of moves required to do so.

One can prove that you can always make all the cells white under the given constraints.

Constraints

• 1 \leq H,W \leq 4
• H\times W\geq 2
• H and W are integers.
• S_{i,j} is . or #.

Sample Input 1

4 4
.#..
....
.#..
....

Sample Output 1

4

By making four moves (1,1)\to(1,2)\to(2,2)\to(3,2)\to(2,2), you can make all the cells white.

Sample Input 2

3 2
..
..
..

Sample Output 2

0

All the cells are initially white, so no moves are required.

Sample Input 3

4 4
#..#
#.##
....
#.##

Sample Output 3

18

Problem Statement

For a positive integer x, let \rm{ord}_2(x) be the number of times 2 divides x.
For example, \rm{ord}_2(24)=3, \rm{ord}_2(17)=0, and \rm{ord}_2(32)=5.

You are given a length-N sequence of integers A=(A_1,A_2,\dots,A_N).
Find \displaystyle \sum^{N}_{ i=1 } \displaystyle \sum^{N}_{ j=i+1 } \rm{ord}_2(A_i + A_j).

Constraints

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

Sample Input 1

5
2 3 5 7 11

Sample Output 1

12

• \rm{ord}_2(2+3) = \rm{ord}_2(5) = 0
• \rm{ord}_2(2+5) = \rm{ord}_2(7) = 0
• \rm{ord}_2(2+7) = \rm{ord}_2(9) = 0
• \rm{ord}_2(2+11) = \rm{ord}_2(13) = 0
• \rm{ord}_2(3+5) = \rm{ord}_2(8) = 3
• \rm{ord}_2(3+7) = \rm{ord}_2(10) = 1
• \rm{ord}_2(3+11) = \rm{ord}_2(14) = 1
• \rm{ord}_2(5+7) = \rm{ord}_2(12) = 2
• \rm{ord}_2(5+11) = \rm{ord}_2(16) = 4
• \rm{ord}_2(7+11) = \rm{ord}_2(18) = 1

Their sum is 12.

Sample Input 2

2
8 13

Sample Output 2

0

Sample Input 3

10
101736933 345226906 942125603 745512475 134406781 47730141 402464131 460079462 359290644 211134700

Sample Output 3

161

Note that the answer may not fit into 32-bit integer type, which is not exemplified in the samples.

Problem Statement

An integer is written on a blackboard.

Takahashi will perform a procedure consisting of N operations described below. For i = 1, 2, \ldots, N, the i-th operation is represented by a pair of a string s_i and an integer p_i, whose meanings are as follows:

• If s_i is NEGATE, replace the integer on the blackboard with -1 times that integer (ignoring the value p_i).
• If s_i is CHMIN, if the integer on the blackboard is greater than p_i, replace it with p_i.
• If s_i is CHMAX, if the integer on the blackboard is less than p_i, replace it with p_i.

You are given Q queries. For i = 1, 2, \ldots, Q, the i-th query is as follows.

• If the integer initially written on the blackboard before the procedure above is q_i, find the integer finally written on the blackboard after the procedure.

Print the answer for each of the Q queries.

Constraints

• N, Q, p_i, and q_i are integers.
• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• -10^9 \leq p_i, q_i \leq 10^9
• s_i is NEGATE, CHMIN, or CHMAX.

Sample Input 1

4 5
CHMAX 3
NEGATE 5
CHMAX -11
NEGATE -12
2
7
15
9
-6

Sample Output 1

3
7
11
9
3

For the first query, that is, if 2 is initially written on the blackboard before the procedure in the problem statement, the operations proceed as follows:

• In the 1-st operation, the integer on the blackboard 2 is less than 3, so replace it with 3.
• In the 2-nd operation, multiply the integer on the blackboard 3 by -1, replacing it with -3.
• In the 3-rd operation, the integer on the blackboard -3 is no less than -11, so do nothing.
• In the 4-th operation, multiply the integer on the blackboard -3 by -1, replacing it with 3.

Thus, in this case, the integer finally written on the blackboard after the procedure is 3, which is the answer to the 1-st query.

Sample Input 2

15 10
CHMAX -14
CHMIN 12
CHMIN 6
NEGATE 10
CHMAX -8
NEGATE -2
NEGATE -20
NEGATE 14
NEGATE 15
NEGATE 5
NEGATE 12
CHMIN 13
CHMIN 20
CHMIN 16
NEGATE -3
-2
-7
6
-18
-20
-18
14
18
-13
-4

Sample Output 2

-2
-7
6
-13
-13
-13
6
6
-13
-4

Problem Statement

There are N people numbered 1 to N. Person i has A_i candies.

Additionally, you are given M pairs of people (X_1,Y_1),\ldots,(X_M,Y_M) who are on bad terms with each other.

What is the minimum number of groups into which the N people can be divided so that both of the following conditions are satisfied?

• The people in each group have at most S candies in total.
• No two people on bad terms are in the same group.

Constraints

• 1 \leq N \leq 20
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1\leq X_i < Y_i \leq N
• The pairs (X_i,Y_i) are distinct.
• 0 \leq A_i \leq 10^7
• \max_i A_i \leq S \leq 10^9
• All inputs are integers.

Sample Input 1

3 1 10
2 3 4
1 2

Sample Output 1

2

Person 1 and person 2 are on bad terms and thus cannot be in the same group. The conditions are satisfied by dividing them into two groups, one composed only of person 1 and the other composed of persons 2 and 3.

Sample Input 2

5 0 10
2 3 4 10 10

Sample Output 2

3

The conditions are satisfied by dividing them into three groups: one composed of persons 1,2,3, one composed only of person 4, and one composed only of person 5.

Sample Input 3

19 10 13639949
6248137 1929297 1115672 3165903 771666 2658398 3460632 3239969 5759071 1396990 5625214 7940774 1755330 7704375 8252319 2891254 3580852 7211614 6847141
11 17
1 11
9 10
10 16
11 19
4 14
2 9
9 19
9 11
17 19

Sample Output 3

7

Problem Statement

Two runners, T and A, are competing in a footrace on a two-dimensional plane. T starts at (T_x,T_y) and runs at a speed of V_T per second. A starts at (A_x,A_y) and runs at a speed of V_A per second.

Once the whistle is blown, they start running simultaneously from their individual starting points toward a common goal. The goal has a fixed x coordinate of 0, but its y coordinate is not determined yet. (Here, it is guaranteed that T_x \neq 0 and A_x \neq 0.)

You want to determine the y coordinate of the goal so that T never loses the race (that is, T reaches the goal first, or the two runners reach the goal at the same time). Let S be the set of y coordinates that achieve the objective.

• If S is empty, print 0;
• if S is non-empty, and S has both the maximum and minimum values, then print the difference between them;
• if S is non-empty, but S does not have both the maximum and minimum values, then print inf.

Constraints

• -10^4 \leq T_x,T_y,A_x,A_y \leq 10^4
• T_x \neq 0
• A_x \neq 0
• 1 \leq V_T,V_A \leq 10^2
• All input values are integers.

Sample Input 1

1 0 1
1 3 2

Sample Output 1

3.464101615137754

We consider two y coordinates of the goal as examples.

• If y=0: it takes \frac{1}{1}=1 seconds for T, and \frac{\sqrt{10}}{2}=1.58\dots seconds for A, to reach the goal.
• If y=2: it takes \frac{\sqrt{5}}{1}=2.23\dots seconds for T, and \frac{\sqrt{2}}{2}=0.70\dots seconds for A, to reach the goal.

One can prove that T reaches the goal first, or the two runners reach the goal at the same time if and only if -1-\sqrt{3} \leq y \leq -1+\sqrt{3}.
Thus, the maximum value of S is -1+\sqrt{3}, and its minimum value is -1-\sqrt{3}, so the answer is (-1+\sqrt{3})-(-1-\sqrt{3})=2\sqrt{3}=3.46\dots.

Sample Input 2

3 0 1
3 3 2

Sample Output 2

0

Regardless of the y coordinate of the goal, A always reaches the goal earlier than T, so S is empty.

Sample Input 3

4 -10 10
-1 3 5

Sample Output 3

inf

S has neither the maximum nor minimum value.

Problem Statement

N ants numbered 1 through N are on a number line, whose positive direction points to the right. In the initial state, ant i is at the initial coordinate X_i and facing the direction described by a character D_i. Specifically, D_i= R means it is facing right, and D_i= L means it is facing left. Here, it is guaranteed that X_1,X_2,\dots, and X_N are pairwise distinct even numbers.

Once Snuke snaps his fingers, the ants starts moving according to the following rules.

• Each ant moves at a speed of 1 per second in the direction it is facing.
• Whenever two ants reach the same coordinate, they flip their directions and continue moving. This event is called a collision of ants. One can prove that three or more ants never reach the same coordinate at the same time.

You are given a total of Q queries, each of one of the following types. Process them in order.

• 1 x d : Add an ant with initial coordinate x and initial direction d to the initial state. Here, it is guaranteed that x is even and does not coincide with the initial coordinate of any ant.
• 2 l r : If Snuke snaps his fingers at time 0, let t_1,t_2,\dots be the times at which ant 1 collides with the other ants, listed in chronological order. Evaluate t_{l}+t_{l+1}+\dots +t_{r} and print it. It is guaranteed that l \leq r and ant 1 collides with the other ants at least r times.

Note that queries of the second type are independent. In other words, processing a query of the second type does not actually modify the initial states of the ants.

Constraints

• N and Q are integers.
• 1\leq N,Q \leq 10^5
• X_i is even.
• |X_i| \leq 10^9
• X_i \neq X_j\ (i \neq j)
• D_i is R or L.
• For each query of the first kind,
  • x is even.
  • |x| \leq 10^9
  • At the point the query is processed, there is no ant with initial coordinate x.
  • d is R or L.
• For each query of the second kind,
  • l and r are integers.
  • 1 \leq l \leq r \leq M, where M is the number of times ant 1 collides with the other ants, starting from the initial state at the point the query is processed.

Sample Input 1

2 5
2 R
10 L
2 1 1
1 0 L
1 -2 R
2 1 2
2 2 2

Sample Output 1

4
10
6

If Snuke snaps his fingers in the initial state before the queries are processed, the ants move as follows.

• At time 0, all the ants start moving. The two ants are facing right and left.
• At time 4\ (:=t_1), ants 1 and 2 collide at coordinate 6. Now the two ants are facing left and right.

Thus, the answer to the 1-st query is t_1=4.

If Snuke snaps his fingers in the initial state where the first three queries are processed, the ants move as follows. Here we call the ants added by the 2-nd and 3-rd query ant 3 and ant 4, respectively.

• At time 0, all the ants start moving. The four ants are facing right, left, left, and right.
• At time 1, ants 3 and 4 collides at coordinate -1. Now, the four ants are facing right, left, right, and left.
• At time 4\ (:=t_1), ants 1 and 2 collides at coordinate 6. Now, the four ants are facing left, right, right, and left.
• At time 6\ (:=t_2), ants 1 and 3 collides at coordinate 4. Now, the four ants are facing right, right, left, and left.

Therefore, the answer to the 4-th query is t_1+t_2=10, and the answer to the 5-th query is t_2=6.

Sample Input 2

10 10
0 R
16 L
94 L
-96 R
-24 L
52 R
-10 L
-38 L
50 R
98 L
1 -66 L
2 2 3
1 48 L
1 34 R
2 2 2
1 8 L
2 2 3
2 2 3
1 62 L
2 1 3

Sample Output 2

151
56
108
108
112