A - T or T

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

タクシーを使うと N 人で B 円かかります。

### 制約

• 入力は全て整数である。
• 1 \leq N \leq 20
• 1 \leq A \leq 50
• 1 \leq B \leq 50

### 入力

N A B


### 入力例 1

4 2 9


### 出力例 1

8


### 入力例 2

4 2 7


### 出力例 2

7


### 入力例 3

4 2 8


### 出力例 3

8


Score : 100 points

### 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

### Input

Input is given from Standard Input in the following format:

N A B


### Output

Print an integer representing the minimum total travel expense.

### 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

B - Roller Coaster

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \le N \le 10^5
• 1 \le K \le 500
• 1 \le h_i \le 500
• 入力はすべて整数

### 入力

N K
h_1 h_2 \ldots h_N


### 入力例 1

4 150
150 140 100 200


### 出力例 1

2


### 入力例 2

1 500
499


### 出力例 2

0


### 入力例 3

5 1
100 200 300 400 500


### 出力例 3

5


Score : 200 points

### 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.

### Input

Input is given from Standard Input in the following format:

N K
h_1 h_2 \ldots h_N


### Output

Print the number of people among the Takahashi's friends who can ride the roller coaster.

### 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

C - Time Limit Exceeded

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

スマートウォッチであるあなたは、N 個の帰宅経路を見つけました。

X さんが i 番目の経路を使う場合、コスト c_i かけて時間 t_i で帰宅できます。

### 制約

• 入力はすべて整数である
• 1 \leq N \leq 100
• 1 \leq T \leq 1000
• 1 \leq c_i \leq 1000
• 1 \leq t_i \leq 1000
• (c_i, t_i) の組は異なる

### 入力

N T
c_1 t_1
c_2 t_2
:
c_N t_N


### 出力

ただし、どの経路を使っても時間 T 以内に帰宅できない場合、TLE と出力せよ。

### 入力例 1

3 70
7 60
1 80
4 50


### 出力例 1

4

• 1 番目の経路を使うと、コスト 7 で帰宅できます
• 2 番目の経路では時間 T = 70 以内に帰宅できません
• 3 番目の経路を使うと、コスト 4 で帰宅できます

### 入力例 2

4 3
1 1000
2 4
3 1000
4 500


### 出力例 2

TLE


どの経路を使っても時間 T = 3 以内に帰宅できません。

### 入力例 3

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


### 出力例 3

5


Score : 200 points

### 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.

### Input

Input is given from Standard Input in the following format:

N T
c_1 t_1
c_2 t_2
:
c_N t_N


### Output

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

If there is no route that takes not longer than time T, print TLE instead.

### 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

D - Unification

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら 2 個のキューブを取り除く操作を何度でも行えます。

このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。

### 制約

• 1 \leq N \leq 10^5
• |S| = N
• S の各文字は 0 または 1 である。

### 入力

S


### 入力例 1

0011


### 出力例 1

4


• 下から 2 番目のキューブと 3 番目のキューブを取り除きます。その結果、下から 4 番目のキューブが下から 1 番目のキューブの上に落下します。
• 下から 1 番目のキューブと 2 番目のキューブを取り除きます。

### 入力例 2

11011010001011


### 出力例 2

12


### 入力例 3

0


### 出力例 3

0


Score : 300 points

### 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.

### Input

Input is given from Standard Input in the following format:

S


### Output

Print the maximum number of cubes that can be removed.

### 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

E - ID

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

Atcoder国には N 個の県があり、これらの県には合計で M 個の市が属しています。

i が誕生したのは Y_i 年であり、県 P_i に属しています。

ただし、同じ年に誕生した市が複数存在することはないとします。

それぞれの市に 12 桁の認識番号を割り振ることとなりました。

i が 県 P_i に属する市の中で x 番目に誕生した市のとき、市 i の認識番号の上 6 桁は P_i、下 6 桁は x となります。

ただし、P_ix6 桁に満たない場合は 6 桁になるまで 0 を左に追加するものとします。

ただし、市が 1 つも属さない県がある場合に注意してください。

### 制約

• 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 は全て異なる
• 入力は全て整数

### 入力

N M
P_1 Y_1
:
P_M Y_M


### 入力例 1

2 3
1 32
2 63
1 12


### 出力例 1

000001000002
000002000001
000001000001

• 1 は県 1 に属する市の中で 2 番目に誕生したので、認識番号は 000001000002 となります。
• 2 は県 2 に属する市の中で 1 番目に誕生したので、認識番号は 000002000001 となります。
• 3 は県 1 に属する市の中で 1 番目に誕生したので、認識番号は 000001000001 となります。

### 入力例 2

2 3
2 55
2 77
2 99


### 出力例 2

000002000001
000002000002
000002000003


Score: 300 points

### 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.

### Input

Input is given from Standard Input in the following format:

N M
P_1 Y_1
:
P_M Y_M


### Output

Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, ...).

### 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

F - Green Bin

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 個の文字列 s_1, s_2, \ldots, s_N が与えられます。それぞれの文字列は長さが 10 で英小文字からなり、またこれらの文字列はすべて異なります。二つの整数 i, j (1 \leq i < j \leq N) の組であって、s_is_j のアナグラムであるようなものの個数を求めてください。

### 制約

• 2 \leq N \leq 10^5
• s_i は長さ 10 の文字列である。
• s_i の各文字は英小文字である。
• s_1, s_2, \ldots, s_N はすべて異なる。

### 入力

N
s_1
s_2
:
s_N


### 入力例 1

3
acornistnt
peanutbomb
constraint


### 出力例 1

1


s_1 = acornistnts_3 = constraint のアナグラムです。他に s_is_j のアナグラムであるような i, j の組はないため、答えは 1 です。

### 入力例 2

2
oneplustwo
ninemodsix


### 出力例 2

0


s_is_j のアナグラムであるような i, j の組がないときは 0 と出力してください。

### 入力例 3

5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa


### 出力例 3

4


ここにそのようなケースを置くことはできませんが、答えは 32 bit 整数型に収まらない可能性があるので注意してください。

Score : 300 points

### 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.

### Input

Input is given from Standard Input in the following format:

N
s_1
s_2
:
s_N


### Output

Print the number of pairs of integers i, j (1 \leq i < j \leq N) such that s_i is an anagram of s_j.

### 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.

G - Enough Array

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• (条件) 連続部分列に含まれる全ての要素の値の和は、K 以上である。

ただし、ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えるものとします。

### 制約

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

### 入力

N K
a_1 a_2 ... a_N


### 入力例 1

4 10
6 1 2 7


### 出力例 1

2

• A[1..4]=a_1,a_2,a_3,a_4 (要素の値の和は 16)
• A[2..4]=a_2,a_3,a_4 (要素の値の和は 10)

の二通りです。

### 入力例 2

3 5
3 3 3


### 出力例 2

3


ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えることに注意してください。

### 入力例 3

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


### 出力例 3

36


Score : 400 points

### 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}

### Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N


### Output

Print the number of contiguous subsequences of A that satisfy the condition.

### 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

H - Powerful Discount Tickets

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

i 番目に買う品物の値段は A_i 円です。

X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を \frac{X}{2^Y} 円(小数点以下切り捨て)で買うことができます。

### 制約

• 入力は全て整数である。
• 1 \leq N, M \leq 10^5
• 1 \leq A_i \leq 10^9

### 入力

N M
A_1 A_2 ... A_N


### 入力例 1

3 3
2 13 8


### 出力例 1

9


• 1 番目に買う品物には割引券を使わず、2 円で買います。
• 2 番目に買う品物には 2 枚の割引券を使い、3 円で買います。
• 3 番目に買う品物には 1 枚の割引券を使い、4 円で買います。

### 入力例 2

4 4
1 9 3 5


### 出力例 2

6


### 入力例 3

1 100000
1000000000


### 出力例 3

0


1000000000 円の品物を買う際に 100000 枚の割引券を使うと 0 円で買うことができます。

### 入力例 4

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


### 出力例 4

9500000000


Score : 400 points

### 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

### Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N


### Output

Print the minimum amount of money required to buy all the items.

### 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

I - Lamp

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

H 行横 W 列のグリッドが与えられます。このグリッドのうち、いくつかのマスには障害物が存在します。

すぬけ君は、障害物のないマスのうち一つを選び、そのマスに明かりを設置しようとしています。 設置されたマスから、上下左右の四方向にまっすぐに光線が伸びます。それぞれの方向について、最初に障害物が存在するマスにぶつかる、もしくはグリッドの端にぶつかる手前のマスまで照らされます。明かりを設置したマスも照らされますが、障害物が存在するマスは照らされません。

すぬけ君は明かりによって照らされるマスの個数を最大化したいです。

H 個の長さ W の文字列 S_i (1 ≤ i ≤ H) が与えられます。S_ij 文字目 (1 ≤ j ≤ W) が # のとき、グリッドの上から i 行目で左から j 列目のマスには障害物があり、 . のときは障害物がありません。

### 制約

• 1 ≤ H ≤ 2,000
• 1 ≤ W ≤ 2,000
• S_i#. のみからなる長さ W の文字列
• S_i (1 ≤ i ≤ H) のうちいずれかに . は最低 1 つ存在する

### 入力

H W
S_1
:
S_H


### 入力例 1

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


### 出力例 1

8


すぬけ君が上から 2 行目、左から 2 列目のマスに明かりを設置すると、上から 2 行目のうち左から 15 列目のマス、 左から 2 列目のうち上から 14 列目のマス全てが照らされ、全部で 8 マスです。

### 入力例 2

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


### 出力例 2

13


Score : 400 points

### 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).

### Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H


### Output

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

### 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

J - Get Everything

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 入力は全て整数
• 1 ≤ N ≤ 12
• 1 ≤ M ≤ 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

### 入力

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}


### 入力例 1

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


### 出力例 1

25


1 と鍵 2 を購入すると、全ての宝箱を開けることが出来ます。このときの費用は 25 円であり、これが最小値です。

### 入力例 2

12 1
100000 1
2


### 出力例 2

-1


### 入力例 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


### 出力例 3

69942


Score : 500 points

### 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

### Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}


### Output

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

### 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

K - Strings of Impurity

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• s10^{100} 個連結して得られる文字列を s' とする。t は、文字列 {s'}_1{s'}_2\ldots{s'}_i (s' の先頭 i 文字) の部分列である。

### 注記

• 文字列 a の部分列とは、a から 0 文字以上を削除して残った文字を相対的な順序を保ったまま連結して得られる文字列です。例えば、contest の部分列には net, c, contest などがあります。

### 制約

• 1 \leq |s| \leq 10^5
• 1 \leq |t| \leq 10^5
• s, t は英小文字からなる。

### 入力

s
t


### 入力例 1

contest
son


### 出力例 1

10


t = son は文字列 contestcon (s' = contestcontestcontest... の先頭 10 文字) の部分列であるため、i = 10 は条件を満たします。

### 入力例 2

contest
programming


### 出力例 2

-1


t = programmings' = contestcontestcontest... の部分列ではありません。よって、条件を満たす整数 i は存在しません。

### 入力例 3

contest
sentence


### 出力例 3

33


ここにそのようなケースを置くことはできませんが、答えは 32 bit 整数に収まらない可能性があるのでご注意ください。

Score : 500 points

### 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.

### Input

Input is given from Standard Input in the following format:

s
t


### Output

If there exists an integer i satisfying the following condition, print the minimum such i; otherwise, print -1.

### 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.

L - League

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

N 人の選手がテニスの大会に参加します。彼らを選手 1、選手 2\ldots、選手 N と呼びます。

• 各選手は一日に最大で一試合を行う。
• 各選手 i (1 \leq i \leq N) は、選手 A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} とこの順に一度ずつ試合を行う。

### 制約

• 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} はすべて異なる。

### 入力

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}


### 入力例 1

3
2 3
1 3
1 2


### 出力例 1

3


3 日間で次のように試合を行えばすべての条件を満たせます。

• 1 日目: 選手 1 対 選手 2
• 2 日目: 選手 1 対 選手 3
• 3 日目: 選手 2 対 選手 3

これが必要な最小日数です。

### 入力例 2

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


### 出力例 2

4


4 日間で次のように試合を行えばすべての条件を満たせます。

• 1 日目: 選手 1 対 選手 2、選手 3 対 選手 4
• 2 日目: 選手 1 対 選手 3
• 3 日目: 選手 1 対 選手 4、選手 2 対 選手 3
• 4 日目: 選手 2 対 選手 4

これが必要な最小日数です。

### 入力例 3

3
2 3
3 1
1 2


### 出力例 3

-1


どのような日程で試合を行っても何らかの条件に違反します。

Score : 500 points

### 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.

### Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}


### Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

### 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.

M - Absolute Minima

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

Q 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。

• 更新クエリ 1 a b:　2整数 a, b が与えられるので、g(x) = f(x) + |x - a| + b として f(x)g(x) で置き換える。
• 求値クエリ 2:　f(x) の最小値を与える x、および f(x) の最小値を出力する。ただし、そのような x が複数存在する場合には最小の x を答える。

この時、求値クエリにおいて出力すべき値は常に整数となることが示せます。 したがって、出力する際は小数点を用いず、整数で出力してください。

### 制約

• 入力は全て整数
• 1 \leq Q \leq 2 \times 10^5
• -10^9 \leq a, b \leq 10^9
• 1 番目のクエリは更新クエリである

### 入力

Q
Query_1
:
Query_Q


### 入力例 1

4
1 4 2
2
1 1 -8
2


### 出力例 1

4 2
1 -3


1 つ目の求値クエリにおいて、f(x) = |x - 4| + 2 となっています。 したがって x = 4 において最小値 2 を取ります。

2 つ目の求値クエリでは、f(x) = |x - 1| + |x - 4| - 6 となっており、x1 \leq x \leq 4 を満たすならば最小値 -3 を与えます。この時、最小値を与える x が複数存在していますが、その中で最小の値である 1 を出力してください。

### 入力例 2

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


### 出力例 2

-1000000000 3000000000


Score : 600 points

### 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.

### Input

Input is given from Standard Input in the following format:

Q
Query_1
:
Query_Q


See Sample Input 1 for an example.

### Output

For each evaluation query, print a line containing the response, in the order in which the queries are given.

The response to each evaluation query should be the minimum value of x that minimizes f(x), and the minimum value of f(x), in this order, with space in between.

### 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

N - Colorful Tree

Time Limit: 4 sec / Memory Limit: 1024 MB

### 問題文

1 から N までの番号がつけられた N 個の頂点を持つ木があります。 この木の i 番目の辺は頂点 a_i と頂点 b_i を結び、その色は c_i、長さは d_i です。 ここで各辺の色は 1 以上 N-1 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。

• j (1 \leq j \leq Q): 色 x_j のすべての辺の長さが y_j に変更されたと仮定して、二頂点 u_j, v_j 間の距離を求めよ。(辺の長さの変更はこれ以降の問いには影響しない。)

### 制約

• 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
• 与えられるグラフは木である。
• 入力中のすべての値は整数である。

### 入力

N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q


### 出力

Q 行出力せよ。j 行目 (1 \leq j \leq Q) に問 j への回答を出力すること。

### 入力例 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


### 出力例 1

130
200
60


この入力中のグラフは次のようなものです。

ここで、色 1 の辺は赤い実線で、色 2 の辺は緑の太線で、色 4 の辺は青い破線で示されています。

• 1: 色 1 のすべての辺の長さが 100 に変更されたと仮定すると、頂点 1, 4 間の距離は 100 + 30 = 130 です。
• 2: 色 1 のすべての辺の長さが 100 に変更されたと仮定すると、頂点 1, 5 間の距離は 100 + 100 = 200 です。
• 3: 色 3 のすべての辺の長さが 1000 に変更されたと仮定すると (そのような辺は存在しません)、頂点 3, 4 間の距離は 20 + 10 + 30 = 60 です。この問いでは色 1 の辺の長さが元に戻っていることに注意してください。

Score : 600 points

### 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.

• 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.

### Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q


### Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.

### 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.
O - Enclosed Points

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

2 次元平面上の N 個の点からなる集合 S があり、i 番目の点の座標は (x_i, y_i) です。N 個の点の x 座標、y 座標はそれぞれ相異なります。

S の空でない部分集合 T に対して f(T) を、各辺が座標軸と平行であって T の点を全て含むような最小の長方形に含まれる点の個数として定義します。より正確には、

• f(T) := T に含まれる点について x 座標の最小値と最大値を それぞれ a, b, そして y 座標の最小値と最大値をそれぞれ c, d としたとき、a \leq x_i \leq b かつ c \leq y_i \leq d を満たす 1 \leq i \leq N の個数

S の空でない全ての部分集合 T についての f(T) の和を計算してください。答えは非常に大きくなることがあるので、998244353 で割った余りを出力してください。

### 制約

• 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)
• 入力は全て整数である

### 入力

N
x_1 y_1
:
x_N y_N


### 出力

S の空でない全ての部分集合 T についての f(T) の和を 998244353 で割った余りを出力せよ。

### 入力例 1

3
-1 3
2 1
3 -2


### 出力例 1

13


1, 2, 3 番目の点をそれぞれ P_1, P_2, P_3 とします。S = \{P_1, P_2, P_3\} の空でない部分集合は 7 個あり、それぞれに対する f の値は次の通りです。

• 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

これらの和は 13 です。

### 入力例 2

4
1 4
2 1
3 3
4 2


### 出力例 2

34


### 入力例 3

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


### 出力例 3

7222


Score : 600 points

### 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.

### Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N


### Output

Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

### 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.