Problem Statement

N of us are going on a trip, by train or taxi.

The train will cost each of us A yen (the currency of Japan).

The taxi will cost us a total of B yen.

How much is our minimum total travel expense?

Constraints

• All values in input are integers.
• 1 \leq N \leq 20
• 1 \leq A \leq 50
• 1 \leq B \leq 50

Sample Input 1

4 2 9

Sample Output 1

8

The train will cost us 4 \times 2 = 8 yen, and the taxi will cost us 9 yen, so the minimum total travel expense is 8 yen.

Sample Input 2

4 2 7

Sample Output 2

7

Sample Input 3

4 2 8

Sample Output 3

8

Problem Statement

N friends of Takahashi has come to a theme park.

To ride the most popular roller coaster in the park, you must be at least K centimeters tall.

The i-th friend is h_i centimeters tall.

How many of the Takahashi's friends can ride the roller coaster?

Constraints

• 1 \le N \le 10^5
• 1 \le K \le 500
• 1 \le h_i \le 500
• All values in input are integers.

Sample Input 1

4 150
150 140 100 200

Sample Output 1

2

Two of them can ride the roller coaster: the first and fourth friends.

Sample Input 2

1 500
499

Sample Output 2

0

Sample Input 3

5 1
100 200 300 400 500

Sample Output 3

5

Problem Statement

When Mr. X is away from home, he has decided to use his smartwatch to search the best route to go back home, to participate in ABC.

You, the smartwatch, has found N routes to his home.

If Mr. X uses the i-th of these routes, he will get home in time t_i at cost c_i.

Find the smallest cost of a route that takes not longer than time T.

Constraints

• All values in input are integers.
• 1 \leq N \leq 100
• 1 \leq T \leq 1000
• 1 \leq c_i \leq 1000
• 1 \leq t_i \leq 1000
• The pairs (c_i, t_i) are distinct.

Sample Input 1

3 70
7 60
1 80
4 50

Sample Output 1

4

• The first route gets him home at cost 7.
• The second route takes longer than time T = 70.
• The third route gets him home at cost 4.

Thus, the cost 4 of the third route is the minimum.

Sample Input 2

4 3
1 1000
2 4
3 1000
4 500

Sample Output 2

TLE

There is no route that takes not longer than time T = 3.

Sample Input 3

5 9
25 8
5 9
4 10
1000 1000
6 1

Sample Output 3

5

Problem Statement

There are N cubes stacked vertically on a desk.

You are given a string S of length N. The color of the i-th cube from the bottom is red if the i-th character in S is 0, and blue if that character is 1.

You can perform the following operation any number of times: choose a red cube and a blue cube that are adjacent, and remove them. Here, the cubes that were stacked on the removed cubes will fall down onto the object below them.

At most how many cubes can be removed?

Constraints

• 1 \leq N \leq 10^5
• |S| = N
• Each character in S is 0 or 1.

Sample Input 1

0011

Sample Output 1

4

All four cubes can be removed, by performing the operation as follows:

• Remove the second and third cubes from the bottom. Then, the fourth cube drops onto the first cube.
• Remove the first and second cubes from the bottom.

Sample Input 2

11011010001011

Sample Output 2

12

Sample Input 3

0

Sample Output 3

0

Problem Statement

In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.

City i is established in year Y_i and belongs to Prefecture P_i.

You can assume that there are no multiple cities that are established in the same year.

It is decided to allocate a 12-digit ID number to each city.

If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P_i, and the last six digits of the ID number is x.

Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.

Find the ID numbers for all the cities.

Note that there can be a prefecture with no cities.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq P_i \leq N
• 1 \leq Y_i \leq 10^9
• Y_i are all different.
• All values in input are integers.

Sample Input 1

2 3
1 32
2 63
1 12

Sample Output 1

000001000002
000002000001
000001000001

• As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
• As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
• As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.

Sample Input 2

2 3
2 55
2 77
2 99

Sample Output 2

000002000001
000002000002
000002000003

Problem Statement

We will call a string obtained by arranging the characters contained in a string a in some order, an anagram of a.

For example, greenbin is an anagram of beginner. As seen here, when the same character occurs multiple times, that character must be used that number of times.

Given are N strings s_1, s_2, \ldots, s_N. Each of these strings has a length of 10 and consists of lowercase English characters. Additionally, all of these strings are distinct. Find the number of pairs of integers i, j (1 \leq i < j \leq N) such that s_i is an anagram of s_j.

Constraints

• 2 \leq N \leq 10^5
• s_i is a string of length 10.
• Each character in s_i is a lowercase English letter.
• s_1, s_2, \ldots, s_N are all distinct.

Sample Input 1

3
acornistnt
peanutbomb
constraint

Sample Output 1

1

s_1 = acornistnt is an anagram of s_3 = constraint. There are no other pairs i, j such that s_i is an anagram of s_j, so the answer is 1.

Sample Input 2

2
oneplustwo
ninemodsix

Sample Output 2

0

If there is no pair i, j such that s_i is an anagram of s_j, print 0.

Sample Input 3

5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa

Sample Output 3

4

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.

Problem Statement

You are given a sequence of positive integers of length N, A=a_1,a_2,…,a_{N}, and an integer K. How many contiguous subsequences of A satisfy the following condition?

• (Condition) The sum of the elements in the contiguous subsequence is at least K.

We consider two contiguous subsequences different if they derive from different positions in A, even if they are the same in content.

Note that the answer may not fit into a 32-bit integer type.

Constraints

• 1 \leq a_i \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^{10}

Sample Input 1

4 10
6 1 2 7

Sample Output 1

2

The following two contiguous subsequences satisfy the condition:

• A[1..4]=a_1,a_2,a_3,a_4, with the sum of 16
• A[2..4]=a_2,a_3,a_4, with the sum of 10

Sample Input 2

3 5
3 3 3

Sample Output 2

3

Note again that we consider two contiguous subsequences different if they derive from different positions, even if they are the same in content.

Sample Input 3

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

Sample Output 3

36

Problem Statement

Takahashi is going to buy N items one by one.

The price of the i-th item he buys is A_i yen (the currency of Japan).

He has M discount tickets, and he can use any number of them when buying an item.

If Y tickets are used when buying an item priced X yen, he can get the item for \frac{X}{2^Y} (rounded down to the nearest integer) yen.

What is the minimum amount of money required to buy all the items?

Constraints

• All values in input are integers.
• 1 \leq N, M \leq 10^5
• 1 \leq A_i \leq 10^9

Sample Input 1

3 3
2 13 8

Sample Output 1

9

We can buy all the items for 9 yen, as follows:

• Buy the 1-st item for 2 yen without tickets.
• Buy the 2-nd item for 3 yen with 2 tickets.
• Buy the 3-rd item for 4 yen with 1 ticket.

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.

Sample Input 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

9500000000

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it. The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right. In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

• 1 \leq H \leq 2,000
• 1 \leq W \leq 2,000
• S_i is a string of length W consisting of # and ..
• . occurs at least once in one of the strings S_i (1 \leq i \leq H).

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13

Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

• All values in input are integers.
• 1 \leq N \leq 12
• 1 \leq M \leq 10^3
• 1 \leq a_i \leq 10^5
• 1 \leq b_i \leq N
• 1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

Sample Output 3

69942

Problem Statement

Given are two strings s and t consisting of lowercase English letters. Determine if there exists an integer i satisfying the following condition, and find the minimum such i if it exists.

• Let s' be the concatenation of 10^{100} copies of s. t is a subsequence of the string {s'}_1{s'}_2\ldots{s'}_i (the first i characters in s').

Notes

• A subsequence of a string a is a string obtained by deleting zero or more characters from a and concatenating the remaining characters without changing the relative order. For example, the subsequences of contest include net, c, and contest.

Constraints

• 1 \leq |s| \leq 10^5
• 1 \leq |t| \leq 10^5
• s and t consists of lowercase English letters.

Sample Input 1

contest
son

Sample Output 1

10

t = son is a subsequence of the string contestcon (the first 10 characters in s' = contestcontestcontest...), so i = 10 satisfies the condition.

On the other hand, t is not a subsequence of the string contestco (the first 9 characters in s'), so i = 9 does not satisfy the condition.

Similarly, any integer less than 9 does not satisfy the condition, either. Thus, the minimum integer i satisfying the condition is 10.

Sample Input 2

contest
programming

Sample Output 2

-1

t = programming is not a substring of s' = contestcontestcontest.... Thus, there is no integer i satisfying the condition.

Sample Input 3

contest
sentence

Sample Output 3

33

Note that the answer may not fit into a 32-bit integer type, though we cannot put such a case here.

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total. Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

• Each player plays at most one matches in a day.
• Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

• 3 \leq N \leq 1000
• 1 \leq A_{i, j} \leq N
• A_{i, j} \neq i
• A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

• Day 1: Player 1 vs Player 2
• Day 2: Player 1 vs Player 3
• Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

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

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

• Day 1: Player 1 vs Player 2, Player 3 vs Player 4
• Day 2: Player 1 vs Player 3
• Day 3: Player 1 vs Player 4, Player 2 vs Player 3
• Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.

Problem Statement

There is a function f(x), which is initially a constant function f(x) = 0.

We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:

• An update query 1 a b: Given two integers a and b, let g(x) = f(x) + |x - a| + b and replace f(x) with g(x).
• An evaluation query 2: Print x that minimizes f(x), and the minimum value of f(x). If there are multiple such values of x, choose the minimum such value.

We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.

Constraints

• All values in input are integers.
• 1 \leq Q \leq 2 \times 10^5
• -10^9 \leq a, b \leq 10^9
• The first query is an update query.

Sample Input 1

4
1 4 2
2
1 1 -8
2

Sample Output 1

4 2
1 -3

In the first evaluation query, f(x) = |x - 4| + 2, which attains the minimum value of 2 at x = 4.

In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6, which attains the minimum value of -3 when 1 \leq x \leq 4. Among the multiple values of x that minimize f(x), we ask you to print the minimum, that is, 1.

Sample Input 2

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

Sample Output 2

-1000000000 3000000000

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively. Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

• Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq a_i, b_i \leq N
• 1 \leq c_i \leq N-1
• 1 \leq d_i \leq 10^4
• 1 \leq x_j \leq N-1
• 1 \leq y_j \leq 10^4
• 1 \leq u_j < v_j \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

Sample Output 1

130
200
60

The graph in this input is as follows:

Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.

• Query 1: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 4 is 100 + 30 = 130.
• Query 2: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 5 is 100 + 100 = 200.
• Query 3: Assuming that the length of every edge whose color is 3 is changed to 1000 (there is no such edge), the distance between Vertex 3 and Vertex 4 is 20 + 10 + 30 = 60. Note that the edges of Color 1 now have their original lengths.

Problem Statement

We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

• f(T) := (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)

Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq x_i, y_i \leq 10^9
• x_i \neq x_j (i \neq j)
• y_i \neq y_j (i \neq j)
• All values in input are integers.

Sample Input 1

3
-1 3
2 1
3 -2

Sample Output 1

13

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:

• f(\{P_1\}) = 1
• f(\{P_2\}) = 1
• f(\{P_3\}) = 1
• f(\{P_1, P_2\}) = 2
• f(\{P_2, P_3\}) = 2
• f(\{P_3, P_1\}) = 3
• f(\{P_1, P_2, P_3\}) = 3

The sum of these is 13.

Sample Input 2

4
1 4
2 1
3 3
4 2

Sample Output 2

34

Sample Input 3

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

Sample Output 3

7222

Be sure to print the sum modulo 998244353.