Problem Statement

Takahashi is playing a game.

In this game, each time the number of coins you have collected so far becomes a multiple of 100, you get a prize.

Takahashi has collected X coins so far. How many more coins does he need to collect before he gets the next prize? (If X is a multiple of 100, we assume that he has already got the prize for collecting X coins in total.)

Constraints

• 0 \leq X \leq 10^5

Sample Input 1

140

Sample Output 1

60

He gets the next prize when he has collected 200 coins in total. To get it, he needs to collect 60 more coins.

Sample Input 2

1000

Sample Output 2

100

He gets the next prize when he has collected 1100 coins in total.

Problem Statement

We call a string hard-to-read when its odd-positioned (1-st, 3-rd, 5-th, ... from the beginning) characters are all lowercase English letters and its even-positioned characters (2-nd, 4-th, 6-th, ... from the beginning) are all uppercase English letters.

Determine whether a string S is hard-to-read.

Constraints

• S consists of uppercase and lowercase English letters.
• The length of S is between 1 and 1000 (inclusive).

Sample Input 1

dIfFiCuLt

Sample Output 1

Yes

The odd-positioned characters are all lowercase and the even-positioned characters are all uppercase, so it is hard-to-read.

Sample Input 2

eASY

Sample Output 2

No

The 3-rd character is not lowercase, so it is not hard-to-read.

Sample Input 3

a

Sample Output 3

Yes

Problem Statement

For an integer x not less than 0, we define g_1(x), g_2(x), f(x) as follows:

• g_1(x)= the integer obtained by rearranging the digits in the decimal notation of x in descending order
• g_2(x)= the integer obtained by rearranging the digits in the decimal notation of x in ascending order
• f(x)=g_1(x)-g_2(x)

For example, we have g_1(314)=431, g_2(3021)=123, f(271)=721-127=594. Note that the leading zeros are ignored.

Given integers N, K, find a_K in the sequence defined by a_0=N, a_{i+1}=f(a_i)\ (i\geq 0).

Constraints

• 0 \leq N \leq 10^9
• 0 \leq K \leq 10^5
• All values in input are integers.

Sample Input 1

314 2

Sample Output 1

693

We have:

• a_0=314
• a_1=f(314)=431-134=297
• a_2=f(297)=972-279=693

Sample Input 2

1000000000 100

Sample Output 2

0

We have:

• a_0=1000000000
• a_1=f(1000000000)=1000000000-1=999999999
• a_2=f(999999999)=999999999-999999999=0
• a_3=f(0)=0-0=0
• \vdots

Sample Input 3

6174 100000

Sample Output 3

6174

Problem Statement

Given are a string X consisting of 0 through 9, and an integer M.

Let d be the greatest digit in X.

How many different integers not greater than M can be obtained by choosing an integer n not less than d+1 and seeing X as a base-n number?

Constraints

• X consists of 0 through 9.
• The length of X is between 1 and 60 (inclusive).
• X does not begin with a 0.
• 1 \leq M \leq 10^{18}

Sample Input 1

22
10

Sample Output 1

2

The greatest digit in X is 2.

• By seeing X as a base-3 number, we get 8.
• By seeing X as a base-4 number, we get 10.

These two values are the only ones that we can obtain and are not greater than 10.

Sample Input 2

999
1500

Sample Output 2

3

The greatest digit in X is 9.

• By seeing X as a base-10 number, we get 999.
• By seeing X as a base-11 number, we get 1197.
• By seeing X as a base-12 number, we get 1413.

These three values are the only ones that we can obtain and are not greater than 1500.

Sample Input 3

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

Sample Output 3

1

By seeing X as a base-2 number, we get 576460752303423488, which is the only value that we can obtain and are not greater than 1000000000000000000.

Problem Statement

In the Republic of AtCoder, there are N cities numbered 1 through N and M railroads numbered 1 through M.

Railroad i connects City A_i and City B_i bidirectionally. At time 0, K_i, and all subsequent multiples of K_i, a train departs from each of these cities and head to the other city. The time each of these trains takes to reach the destination is T_i.

You are now at City X. Find the earliest time you can reach City Y when you start the journey by taking a train that departs City X not earlier than time 0. If City Y is unreachable, report that fact.
The time it takes to transfer is ignorable. That is, at every city, you can transfer to a train that departs at the exact time your train arrives at that city.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 10^5
• 1 \leq X,Y \leq N
• X \neq Y
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• 1 \leq T_i \leq 10^9
• 1 \leq K_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

7

First, you take Railroad 1 at time 0 and go from City 1 to City 2. You arrive at City 2 at time 2.

Then, you take Railroad 2 at time 4 and go from City 2 to City 3. You arrive at City 3 at time 7.

There is no way to reach City 3 earlier.

Sample Input 2

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

Sample Output 2

5

First, you take Railroad 2 at time 0 and go from City 3 to City 2. You arrive at City 2 at time 3.

Then, you take Railroad 1 at time 3 and go from City 2 to City 1. You arrive at City 1 at time 5.

Sample Input 3

3 0 3 1

Sample Output 3

-1

Sample Input 4

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

Sample Output 4

26

Problem Statement

There are N kinds of materials. Material i has a magic power of A_i.

Takahashi, the magician, wants to make a potion by choosing one or more kinds from these materials and mixing them.

At the moment when he makes a potion by mixing k kinds of materials, the magic power of the potion is the sum of the materials used. Then, every second, its magic power increases by k. Note that the increase of the magic power is a discrete - not continuous - process.

Takahashi will mix materials just once, at time 0. What is the earliest time he can get a potion with a magic power of exactly X?

Under the constraints, it can be proved that it is possible to make a potion with a magic power of exactly X.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^7
• 10^9 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3 9999999999
3 6 8

Sample Output 1

4999999994

The potion made by mixing Material 1 and Material 3 has a magic power of 3+8=11 at time 0, and it increases by 2 every second, so it will be 9999999999 at time 4999999994, which is the earliest possible time.

The potion made by mixing all the materials 1, 2, 3 will have a magic power of 9999999998 at time 3333333327 and 10000000001 at time 3333333328, so it will never be exactly 9999999999.

Sample Input 2

1 1000000000000000000
1

Sample Output 2

999999999999999999