A - Libra

Time Limit: 2 sec / Memory Limit: 256 MB

### 制約

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

### 入力

A B C D


### 入力例 1

3 8 7 1


### 出力例 1

Left


### 入力例 2

3 4 5 2


### 出力例 2

Balanced


### 入力例 3

1 7 6 4


### 出力例 3

Right


Score : 100 points

### Problem Statement

A balance scale tips to the left if L>R, where L is the total weight of the masses on the left pan and R is the total weight of the masses on the right pan. Similarly, it balances if L=R, and tips to the right if L<R.

Takahashi placed a mass of weight A and a mass of weight B on the left pan of a balance scale, and placed a mass of weight C and a mass of weight D on the right pan.

Print Left if the balance scale tips to the left; print Balanced if it balances; print Right if it tips to the right.

### Constraints

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

### Input

Input is given from Standard Input in the following format:

A B C D


### Output

Print Left if the balance scale tips to the left; print Balanced if it balances; print Right if it tips to the right.

### Sample Input 1

3 8 7 1


### Sample Output 1

Left


The total weight of the masses on the left pan is 11, and the total weight of the masses on the right pan is 8. Since 11>8, we should print Left.

### Sample Input 2

3 4 5 2


### Sample Output 2

Balanced


The total weight of the masses on the left pan is 7, and the total weight of the masses on the right pan is 7. Since 7=7, we should print Balanced.

### Sample Input 3

1 7 6 4


### Sample Output 3

Right


The total weight of the masses on the left pan is 8, and the total weight of the masses on the right pan is 10. Since 8<10, we should print Right.

B - Some Sums

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

### 制約

• 1 \leq N \leq 10^4
• 1 \leq A \leq B \leq 36
• 入力はすべて整数である

### 入力

N A B


### 出力

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

### 入力例 1

20 2 5


### 出力例 1

84


20 以下の整数のうち、各桁の和が 2 以上 5 以下なのは 2,3,4,5,11,12,13,14,20 です。これらの合計である 84 を出力します。

### 入力例 2

10 1 2


### 出力例 2

13


### 入力例 3

100 4 16


### 出力例 3

4554


Score : 200 points

### Problem Statement

Find the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

### Constraints

• 1 \leq N \leq 10^4
• 1 \leq A \leq B \leq 36
• All input values are integers.

### Input

Input is given from Standard Input in the following format:

N A B


### Output

Print the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

### Sample Input 1

20 2 5


### Sample Output 1

84


Among the integers not greater than 20, the ones whose sums of digits are between 2 and 5, are: 2,3,4,5,11,12,13,14 and 20. We should print the sum of these, 84.

### Sample Input 2

10 1 2


### Sample Output 2

13


### Sample Input 3

100 4 16


### Sample Output 3

4554


Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

• AX 以上 Y 以下の整数からなる
• すべての 1\leq i \leq |A|-1 に対し、A_{i+1}A_i の倍数であり、かつ A_{i+1}A_i より真に大きい

### 制約

• 1 \leq X \leq Y \leq 10^{18}
• 入力は全て整数である

### 入力

X Y


### 入力例 1

3 20


### 出力例 1

3


### 入力例 2

25 100


### 出力例 2

3


### 入力例 3

314159265 358979323846264338


### 出力例 3

31


Score : 300 points

### Problem Statement

As a token of his gratitude, Takahashi has decided to give his mother an integer sequence. The sequence A needs to satisfy the conditions below:

• A consists of integers between X and Y (inclusive).
• For each 1\leq i \leq |A|-1, A_{i+1} is a multiple of A_i and strictly greater than A_i.

Find the maximum possible length of the sequence.

### Constraints

• 1 \leq X \leq Y \leq 10^{18}
• All input values are integers.

### Input

Input is given from Standard Input in the following format:

X Y


### Output

Print the maximum possible length of the sequence.

### Sample Input 1

3 20


### Sample Output 1

3


The sequence 3,6,18 satisfies the conditions.

### Sample Input 2

25 100


### Sample Output 2

3


### Sample Input 3

314159265 358979323846264338


### Sample Output 3

31

D - Wide Flip

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

01 からなる文字列 S が与えられます。 以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。

• S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r-l+1\geq K が満たされる必要がある)。l\leq i\leq r なるすべての整数 i に対し、S_i0 なら S_i1 に、S_i1 なら S_i0 に置き換える。

### 制約

• 1\leq |S|\leq 10^5
• S_i(1\leq i\leq N)0 または 1 である

### 入力

S


### 入力例 1

010


### 出力例 1

2


• 長さ 3 の区間 [1,3] に操作を行う。S101 になる。
• 長さ 2 の区間 [1,2] に操作を行う。S011 になる。
• 長さ 2 の区間 [2,3] に操作を行う。S000 になる。

### 入力例 2

100000000


### 出力例 2

8


### 入力例 3

00001111


### 出力例 3

4


Score : 500 points

### Problem Statement

You are given a string S consisting of 0 and 1. Find the maximum integer K not greater than |S| such that we can turn all the characters of S into 0 by repeating the following operation some number of times.

• Choose a contiguous segment [l,r] in S whose length is at least K (that is, r-l+1\geq K must be satisfied). For each integer i such that l\leq i\leq r, do the following: if S_i is 0, replace it with 1; if S_i is 1, replace it with 0.

### Constraints

• 1\leq |S|\leq 10^5
• S_i(1\leq i\leq N) is either 0 or 1.

### Input

Input is given from Standard Input in the following format:

S


### Output

Print the maximum integer K such that we can turn all the characters of S into 0 by repeating the operation some number of times.

### Sample Input 1

010


### Sample Output 1

2


We can turn all the characters of S into 0 by the following operations:

• Perform the operation on the segment S[1,3] with length 3. S is now 101.
• Perform the operation on the segment S[1,2] with length 2. S is now 011.
• Perform the operation on the segment S[2,3] with length 2. S is now 000.

### Sample Input 2

100000000


### Sample Output 2

8


### Sample Input 3

00001111


### Sample Output 3

4