A - Sheep and Wolves

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \leq S \leq 100
• 1 \leq W \leq 100

### 入力

S W


### 入力例 1

4 5


### 出力例 1

unsafe


### 入力例 2

100 2


### 出力例 2

safe


### 入力例 3

10 10


### 出力例 3

unsafe


Score : 100 points

### Problem Statement

There are S sheep and W wolves.

If the number of wolves is greater than or equal to that of sheep, the wolves will attack the sheep.

If the wolves will attack the sheep, print unsafe; otherwise, print safe.

### Constraints

• 1 \leq S \leq 100
• 1 \leq W \leq 100

### Input

Input is given from Standard Input in the following format:

S W


### Output

If the wolves will attack the sheep, print unsafe; otherwise, print safe.

### Sample Input 1

4 5


### Sample Output 1

unsafe


There are four sheep and five wolves. The number of wolves is not less than that of sheep, so they will attack them.

### Sample Input 2

100 2


### Sample Output 2

safe


Many a sheep drive away two wolves.

### Sample Input 3

10 10


### Sample Output 3

unsafe

B - Battle

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \leq A,B,C,D \leq 100
• 入力はすべて整数である。

### 入力

A B C D


### 入力例 1

10 9 10 10


### 出力例 1

No


はじめに、高橋君の攻撃で青木君のモンスターの体力が 10-9=1 になります。

### 入力例 2

46 4 40 5


### 出力例 2

Yes


Score : 200 points

### Problem Statement

Takahashi and Aoki will have a battle using their monsters.

The health and strength of Takahashi's monster are A and B, respectively, and those of Aoki's monster are C and D, respectively.

The two monsters will take turns attacking, in the order Takahashi's, Aoki's, Takahashi's, Aoki's, ... Here, an attack decreases the opponent's health by the value equal to the attacker's strength. The monsters keep attacking until the health of one monster becomes 0 or below. The person with the monster whose health becomes 0 or below loses, and the other person wins.

If Takahashi will win, print Yes; if he will lose, print No.

### Constraints

• 1 \leq A,B,C,D \leq 100
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

A B C D


### Output

If Takahashi will win, print Yes; if he will lose, print No.

### Sample Input 1

10 9 10 10


### Sample Output 1

No


First, Takahashi's monster attacks Aoki's monster, whose health is now 10-9=1.

Next, Aoki's monster attacks Takahashi's monster, whose health is now 10-10=0.

Takahashi's monster is the first to have 0 or less health, so Takahashi loses.

### Sample Input 2

46 4 40 5


### Sample Output 2

Yes

C - gacha

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

くじ引きを N 回行い、i 回目には種類が文字列 S_i で表される景品を手に入れました。

### 制約

• 1 \leq N \leq 2\times 10^5
• S_i は英小文字のみからなり、長さは 1 以上 10 以下

### 入力

N
S_1
:
S_N


### 入力例 1

3
apple
orange
apple


### 出力例 1

2


appleorange2 種類の景品を手に入れました。

### 入力例 2

5
grape
grape
grape
grape
grape


### 出力例 2

1


### 入力例 3

4
aaaa
a
aaa
aa


### 出力例 3

4


Score : 300 points

### Problem Statement

You drew lottery N times. In the i-th draw, you got an item of the kind represented by a string S_i.

How many kinds of items did you get?

### Constraints

• 1 \leq N \leq 2\times 10^5
• S_i consists of lowercase English letters and has a length between 1 and 10 (inclusive).

### Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N


### Output

Print the number of kinds of items you got.

### Sample Input 1

3
apple
orange
apple


### Sample Output 1

2


You got two kinds of items: apple and orange.

### Sample Input 2

5
grape
grape
grape
grape
grape


### Sample Output 2

1


### Sample Input 3

4
aaaa
a
aaa
aa


### Sample Output 3

4

D - Multiple of 2019

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から 9 までの数字のみからなる文字列 S が与えられます。

### 制約

• 1 ≤ |S| ≤ 200000
• S1 から 9 までの数字のみからなる文字列

### 入力

S


### 入力例 1

1817181712114


### 出力例 1

3


### 入力例 2

14282668646


### 出力例 2

2


### 入力例 3

2119


### 出力例 3

0


Score : 400 points

### Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

### Constraints

• 1 ≤ |S| ≤ 200000
• S is a string consisting of digits from 1 through 9.

### Input

Input is given from Standard Input in the following format:

S


### Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

### Sample Input 1

1817181712114


### Sample Output 1

3


Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

### Sample Input 2

14282668646


### Sample Output 2

2


### Sample Input 3

2119


### Sample Output 3

0


No pairs satisfy the condition.

E - Two Currencies

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から N までの番号がつけられた N 個の都市があります。 これらの都市は M 本の鉄道路線によって結ばれています。

あなたは現在、金貨を 10^{100} 枚、銀貨を S 枚持った状態で都市 1 にいます。

i 番目の鉄道路線は、都市 U_i と都市 V_i を双方向に結んでおり、片道の運賃は 銀貨 A_i 枚、移動にかかる時間は B_i 分です。 運賃を金貨で払うことはできません。

t=2,...,N について、都市 1 から都市 t への移動にかかる最小の時間を求めてください。電車を待つのにかかる時間は無視して構いません。

### 制約

• 2 \leq N \leq 50
• N-1 \leq M \leq 100
• 0 \leq S \leq 10^9
• 1 \leq A_i \leq 50
• 1 \leq B_i,C_i,D_i \leq 10^9
• 1 \leq U_i < V_i \leq N
• (U_i,V_i)=(U_j,V_j) なる i,j(i \neq j) は存在しない
• 都市 1 から都市 t=2,...,N にいくつかの鉄道路線を使って移動することができる。
• 入力はすべて整数である。

### 入力

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N


### 出力

t=2,...,Nについて、都市 1 から都市 t への移動にかかる最小の時間を順番に一行ずつ出力せよ。

### 入力例 1

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


### 出力例 1

2
14


この入力中の鉄道網は以下のようなものです。

ここで、図中の都市のラベルは

• 一段目に都市の番号 i
• 二段目に C_i / D_i

の形式に従っています。同様に、鉄道路線のラベルは

• 一段目に鉄道路線の番号 i
• 二段目に A_i / B_i

の形式に従っています。

• 1 番目の鉄道路線を使って、都市 1 から都市 2 へ移動する。(所要時間: 2 分)

• 1 番目の鉄道路線を使って、都市 1 から都市 2 へ移動する。(所要時間: 2 分)
• 都市 2 の両替所で、金貨 3 枚を銀貨 3 枚と交換する。(所要時間: 6 分)
• 1 番目の鉄道路線を使って、都市 2 から都市 1 へ移動する。(所要時間: 2 分)
• 2 番目の鉄道路線を使って、都市 1 から都市 3 へ移動する。(所要時間: 4 分)

### 入力例 2

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


### 出力例 2

5
5
7


この入力中の鉄道網は以下のようなものです。

• 都市 1 の両替所で、金貨 2 枚を銀貨 6 枚と交換する。(所要時間: 2 分)
• 2 番目の鉄道路線を使って、都市 1 から都市 3 へ移動する。(所要時間: 4 分)
• 4 番目の鉄道路線を使って、都市 3 から都市 4 へ移動する。(所要時間: 1 分)

### 入力例 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1


### 出力例 3

1
9003
14606
16510
16576


この入力中の鉄道網は以下のようなものです。

• 1 番目の鉄道路線を使って、都市 1 から都市 2 へ移動する。(所要時間: 1 分)
• 都市 2 の両替所で、金貨 3 枚を銀貨 3 枚と交換する。(所要時間: 9000 分)
• 1 番目の鉄道路線を使って、都市 2 から都市 1 へ移動する。(所要時間: 1 分)
• 2 番目の鉄道路線を使って、都市 1 から都市 3 へ移動する。(所要時間: 1 分)
• 都市 3 の両替所で、金貨 8 枚を銀貨 8 枚と交換する。(所要時間: 5600 分)
• 2 番目の鉄道路線を使って、都市 3 から都市 1 へ移動する。(所要時間: 1 分)
• 1 番目の鉄道路線を使って、都市 1 から都市 2 へ移動する。(所要時間: 1 分)
• 3 番目の鉄道路線を使って、都市 2 から都市 4 へ移動する。(所要時間: 1 分)
• 都市 4 の両替所で、金貨 19 枚を銀貨 19 枚と交換する。(所要時間: 1900 分)
• 3 番目の鉄道路線を使って、都市 4 から都市 2 へ移動する。(所要時間: 1 分)
• 1 番目の鉄道路線を使って、都市 2 から都市 1 へ移動する。(所要時間: 1 分)
• 2 番目の鉄道路線を使って、都市 1 から都市 3 へ移動する。(所要時間: 1 分)
• 4 番目の鉄道路線を使って、都市 3 から都市 5 へ移動する。(所要時間: 1 分)
• 都市 5 の両替所で、金貨 63 枚を銀貨 63 枚と交換する。(所要時間: 63 分)
• 4 番目の鉄道路線を使って、都市 5 から都市 3 へ移動する。(所要時間: 1 分)
• 2 番目の鉄道路線を使って、都市 3 から都市 1 へ移動する。(所要時間: 1 分)
• 5 番目の鉄道路線を使って、都市 1 から都市 6 へ移動する。(所要時間: 1 分)

### 入力例 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7


### 出力例 4

1
3
5


この入力中の鉄道網は以下のようなものです。

### 入力例 5

2 1 0
1 2 1 1
1 1000000000
1 1


### 出力例 5

1000000001


この入力中の鉄道網は以下のようなものです。

• 都市 1 の両替所で、金貨 1 枚を銀貨 1 枚と交換する。(所要時間: 1000000000 分)
• 1 番目の鉄道路線を使って、都市 1 から都市 2 へ移動する。(所要時間: 1 分)

Score : 500 points

### Problem Statement

There are N cities numbered 1 to N, connected by M railroads.

You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.

The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes. You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin. The transaction takes D_i minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.

For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.

### Constraints

• 2 \leq N \leq 50
• N-1 \leq M \leq 100
• 0 \leq S \leq 10^9
• 1 \leq A_i \leq 50
• 1 \leq B_i,C_i,D_i \leq 10^9
• 1 \leq U_i < V_i \leq N
• There is no pair i, j(i \neq j) such that (U_i,V_i)=(U_j,V_j).
• Each city t=2,...,N can be reached from City 1 with some number of railroads.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N


### Output

For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.

### Sample Input 1

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


### Sample Output 1

2
14


The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

• The first line: the ID number i of the city (i for City i)
• The second line: C_i / D_i

Similarly, each railroad is labeled as follows:

• The first line: the ID number i of the railroad (i for the i-th railroad in input)
• The second line: A_i / B_i

You can travel from City 1 to City 2 in 2 minutes, as follows:

• Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.

You can travel from City 1 to City 3 in 14 minutes, as follows:

• Use the 1-st railroad to move from City 1 to City 2 in 2 minutes.
• At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 6 minutes.
• Use the 1-st railroad to move from City 2 to City 1 in 2 minutes.
• Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.

### Sample Input 2

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


### Sample Output 2

5
5
7


The railway network in this input is shown in the figure below:

You can travel from City 1 to City 4 in 7 minutes, as follows:

• At the exchange counter in City 1, exchange 2 gold coins for 6 silver coins in 2 minutes.
• Use the 2-nd railroad to move from City 1 to City 3 in 4 minutes.
• Use the 4-th railroad to move from City 3 to City 4 in 1 minutes.

### Sample Input 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1


### Sample Output 3

1
9003
14606
16510
16576


The railway network in this input is shown in the figure below:

You can travel from City 1 to City 6 in 16576 minutes, as follows:

• Use the 1-st railroad to move from City 1 to City 2 in 1 minute.
• At the exchange counter in City 2, exchange 3 gold coins for 3 silver coins in 9000 minutes.
• Use the 1-st railroad to move from City 2 to City 1 in 1 minute.
• Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.
• At the exchange counter in City 3, exchange 8 gold coins for 8 silver coins in 5600 minutes.
• Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.
• Use the 1-st railroad to move from City 1 to City 2 in 1 minute.
• Use the 3-rd railroad to move from City 2 to City 4 in 1 minute.
• At the exchange counter in City 4, exchange 19 gold coins for 19 silver coins in 1900 minutes.
• Use the 3-rd railroad to move from City 4 to City 2 in 1 minute.
• Use the 1-st railroad to move from City 2 to City 1 in 1 minute.
• Use the 2-nd railroad to move from City 1 to City 3 in 1 minute.
• Use the 4-th railroad to move from City 3 to City 5 in 1 minute.
• At the exchange counter in City 5, exchange 63 gold coins for 63 silver coins in 63 minutes.
• Use the 4-th railroad to move from City 5 to City 3 in 1 minute.
• Use the 2-nd railroad to move from City 3 to City 1 in 1 minute.
• Use the 5-th railroad to move from City 1 to City 6 in 1 minute.

### Sample Input 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7


### Sample Output 4

1
3
5


The railway network in this input is shown in the figure below:

### Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1


### Sample Output 5

1000000001


The railway network in this input is shown in the figure below:

You can travel from City 1 to City 2 in 1000000001 minutes, as follows:

• At the exchange counter in City 1, exchange 1 gold coin for 1 silver coin in 1000000000 minutes.
• Use the 1-st railroad to move from City 1 to City 2 in 1 minute.
F - I hate Matrix Construction

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• a_{i,j} は整数である。
• 0 \leq a_{i,j} \lt 2^{64}
• S_{i} = 0 のとき i 行目の要素のビットごとの論理積は U_{i} である。
• S_{i} = 1 のとき i 行目の要素のビットごとの論理和は U_{i} である。
• T_{i} = 0 のとき i 列目の要素のビットごとの論理積は V_{i} である。
• T_{i} = 1 のとき i 列目の要素のビットごとの論理和は V_{i} である。

ただし、条件を満たす行列が存在しない場合もあるかもしれません。

### 制約

• 入力は全て整数
• 1 \leq N \leq 500
• 0 \leq S_{i} \leq 1
• 0 \leq T_{i} \leq 1
• 0 \leq U_{i} \lt 2^{64}
• 0 \leq V_{i} \lt 2^{64}

### 入力

N
S_{1} S_{2} ...  S_{N}
T_{1} T_{2} ...  T_{N}
U_{1} U_{2} ...  U_{N}
V_{1} V_{2} ...  V_{N}


### 出力

a_{1,1} ...  a_{1,N}
:
a_{N,1} ...  a_{N,N}


### 入力例 1

2
0 1
1 0
1 1
1 0


### 出力例 1

1 1
1 0


• 1 行目の要素のビットごとの論理積が 1
• 2 行目の要素のビットごとの論理和が 1
• 1 列目の要素のビットごとの論理和が 1
• 2 列目の要素のビットごとの論理積が 0

の条件を満たす行列を見つける必要があります。

### 入力例 2

2
1 1
1 0
15 15
15 11


### 出力例 2

15 11
15 11


Score : 600 points

### Problem Statement

Given are an integer N and arrays S, T, U, and V, each of length N. Construct an N×N matrix a that satisfy the following conditions:

• a_{i,j} is an integer.
• 0 \leq a_{i,j} \lt 2^{64}.
• If S_{i} = 0, the bitwise AND of the elements in the i-th row is U_{i}.
• If S_{i} = 1, the bitwise OR of the elements in the i-th row is U_{i}.
• If T_{i} = 0, the bitwise AND of the elements in the i-th column is V_{i}.
• If T_{i} = 1, the bitwise OR of the elements in the i-th column is V_{i}.

However, there may be cases where no matrix satisfies the conditions.

### Constraints

• All values in input are integers.
• 1 \leq N \leq 500
• 0 \leq S_{i} \leq 1
• 0 \leq T_{i} \leq 1
• 0 \leq U_{i} \lt 2^{64}
• 0 \leq V_{i} \lt 2^{64}

### Input

Input is given from Standard Input in the following format:

N
S_{1} S_{2} ...  S_{N}
T_{1} T_{2} ...  T_{N}
U_{1} U_{2} ...  U_{N}
V_{1} V_{2} ...  V_{N}


### Output

If there exists a matrix that satisfies the conditions, print one such matrix in the following format:

a_{1,1} ...  a_{1,N}
:
a_{N,1} ...  a_{N,N}


Note that any matrix satisfying the conditions is accepted.

If no matrix satisfies the conditions, print -1.

### Sample Input 1

2
0 1
1 0
1 1
1 0


### Sample Output 1

1 1
1 0


In Sample Input 1, we need to find a matrix such that:

• the bitwise AND of the elements in the 1-st row is 1;
• the bitwise OR of the elements in the 2-nd row is 1;
• the bitwise OR of the elements in the 1-st column is 1;
• the bitwise AND of the elements in the 2-nd column is 0.

### Sample Input 2

2
1 1
1 0
15 15
15 11


### Sample Output 2

15 11
15 11