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

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

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.

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

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

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

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.

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.

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.

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.

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}

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