codeforces AIM Tech Round 3 (Div. 2) （A~D）

A. Juicer

time limit per test

memory limit per test

input

output

Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

Input

The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

Output

Print one integer — the number of times Kolya will have to empty the waste section.

Examples

input

2 7 105 6

output

1

input

1 5 107

output

0

input

3 10 105 7 7

output

1

input

1 1 11

output

0

Note

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

题解：给你n个橙，要选小于等于b的橙做成果汁，如果放进果汁机的橙总和大于d，就要浪费一次。问你把这些橙全部做成果汁后，浪费了多少次。模拟一下就可以了。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

B. Checkpoints

time limit per test

memory limit per test

input

output

Vasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x1, x2, ..., xn. Vasya starts at the point with coordinate a. His goal is to visit at least n - 1

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized. He asks you to calculate this minimum possible value.

Input

The first line of the input contains two integers n and a (1 ≤ n ≤ 100 000,  - 1 000 000 ≤ a ≤ 1 000 000) — the number of checkpoints and Vasya's starting position respectively.

The second line contains n integers x1, x2, ..., xn ( - 1 000 000 ≤ xi) — coordinates of the checkpoints.

Output

Print one integer — the minimum distance Vasya has to travel in order to visit at least n - 1

Examples

input

3 101 7 12

output

7

input

2 011 -10

output

10

input

5 00 0 1000 0 0

output

0

Note

In the first sample Vasya has to visit at least two checkpoints. The optimal way to achieve this is the walk to the third checkpoints (distance is 12 - 10 = 2) and then proceed to the second one (distance is 12 - 7 = 5). The total distance is equal to 2 + 5 = 7.

In the second sample it's enough to visit only one checkpoint so Vasya should just walk to the point  - 10.

题意：给你n个点,要经过n-1个点才算完成比赛，问完成比赛的最小路程。

题解：因为要经过n-1个点，所以只要贪心一下a附近n-1个点就可以啦。

比如下面这图：a附近的X1到Xn-1。

还有的X0到Xn-2也一样。

再选其中路程最短就可以了。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

C. Letters Cyclic Shift

time limit per test

memory limit per test

input

output

You are given a non-empty string s consisting of lowercase English letters. You have to pick exactly one non-empty substring of sand shift all its letters 'z'

'y'

'x'

'b'

'a'

'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from s

Input

The only line of the input contains the string s (1 ≤ |s| ≤ 100 000) consisting of lowercase English letters.

Output

Print the lexicographically minimum string that can be obtained from s

Examples

input

codeforces

output

bncdenqbdr

input

abacaba

output

aaacaba

Note：String s is lexicographically smaller than some other string t of the same length if there exists some 1 ≤ i ≤ |s|, such thats1 = t1, s2 = t2, ..., si - 1 = ti - 1, and si < ti.

题解： 如果不是全部是a，就找到第一个不是a的子串shift。如果全部是a，最后一个a就变成z。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

Examples

input

1 2 3 4

output

Impossible

input

1 2 2 1

output

0110

题意：给你00,01,10,11这四个序列的个数。然后要你构造出合法的01序列。不存在合法的01序列就输出Impossible。

例如：0110有1个00,2个01,2个10,1个11。

题解：因为n*(n-1)=2*a00和m*(m-1)=2*a11和a01+a10=n*m。

所以可以先计算出0和1的数量，接下来先去构造a10，再构造a01就好了。构造题。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。