Codeforces Round #372 (Div. 2) A B C 水暴力/模拟构造

ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!

More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.

For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.

You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.

Input

The first line contains two integers n and c (1 ≤ n ≤ 100 000, 1 ≤ c ≤ 10⁹) — the number of words ZS the Coder typed and the crazy computer delay respectively.

The next line contains n integers t₁, t₂, ..., t_n (1 ≤ t₁ < t₂ < ... < t_n ≤ 10⁹), where t_i denotes the second when ZS the Coder typed the i-th word.

Output

Print a single positive integer, the number of words that remain on the screen after all n words was typed, in other words, at the second t_n.

Examples

Input

6 5
1 3 8 14 19 20

Output

Input

6 1
1 3 5 7 9 10

Output

Note

The first sample is already explained in the problem statement.

For the second sample, after typing the first word at the second 1, it disappears because the next word is typed at the second 3 and 3 - 1 > 1. Similarly, only 1 word will remain at the second 9. Then, a word is typed at the second 10, so there will be two words on the screen, as the old word won't disappear because 10 - 9 ≤ 1.

题意:n个数从左向右遍历相邻的数的差值<=c 则计数++ 否则计数清零输出最后结果

题解：水

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 #include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<queue>
14 #define LL __int64
15 #define pii pair<int,int>
16 #define MP make_pair
17 using namespace std;
18 int n,c;
19 int a[100005];
20 int main()
21 {
22     scanf("%d%d",&n,&c);
23     for(int i=1;i<=n;i++)
24         scanf("%d",&a[i]);
25     int ans=1;
26     int exm=a[n];
27     for(int i=n-1;i>=1;i--)
28     {
29        if((exm-a[i])<=c)
30         {
31         ans++;
32         exm=a[i];
33         }
34         else
35         {
36             break;
37         }
38     }
39     cout<<ans<<endl;
40     return 0;

ZS the Coder loves to read the dictionary. He thinks that a word is nice if there exists a substring (contiguous segment of letters) of it of length 26 where each letter of English alphabet appears exactly once. In particular, if the string has length strictly less than 26, no such substring exists and thus it is not nice.

Now, ZS the Coder tells you a word, where some of its letters are missing as he forgot them. He wants to determine if it is possible to fill in the missing letters so that the resulting word is nice. If it is possible, he needs you to find an example of such a word as well. Can you help him?

Input

The first and only line of the input contains a single string s (1 ≤ |s| ≤ 50 000), the word that ZS the Coder remembers. Each character of the string is the uppercase letter of English alphabet ('A'-'Z') or is a question mark ('?'), where the question marks denotes the letters that ZS the Coder can't remember.

Output

If there is no way to replace all the question marks with uppercase letters such that the resulting word is nice, then print - 1 in the only line.

Otherwise, print a string which denotes a possible nice word that ZS the Coder learned. This string should match the string from the input, except for the question marks replaced with uppercase English letters.

If there are multiple solutions, you may print any of them.

Examples

Input

ABC??FGHIJK???OPQR?TUVWXY?

Output

ABCDEFGHIJKLMNOPQRZTUVWXYS

Input

WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

Output

-1

Input

??????????????????????????

Output

MNBVCXZLKJHGFDSAQPWOEIRUYT

Input

AABCDEFGHIJKLMNOPQRSTUVW??M

Output

-1

Note

In the first sample case, ABCDEFGHIJKLMNOPQRZTUVWXYS is a valid answer beacuse it contains a substring of length 26 (the whole string in this case) which contains all the letters of the English alphabet exactly once. Note that there are many possible solutions, such as ABCDEFGHIJKLMNOPQRSTUVWXYZ or ABCEDFGHIJKLMNOPQRZTUVWXYS.

In the second sample case, there are no missing letters. In addition, the given string does not have a substring of length 26 that contains all the letters of the alphabet, so the answer is - 1.

In the third sample case, any string of length 26 that contains all letters of the English alphabet fits as an answer

题意：给你一个串其中只有大写字母和'?' 现在更改问号位置的字符为大写字母使得存在连续的长度为26的子串含有所有的大写字母

无法实现输出-1 否则输出更改之后的字符串

题解：枚举每个长度为统计

map标记缺少的字母种类的数量必须和当前区间的问号的数量相等

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 #include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<queue>
14 #define LL __int64
15 #define pii pair<int,int>
16 #define MP make_pair
17 using namespace std;
18 char a[50004];
19 map<char,int> mp;
20 int main()
21 {
22     cin>>a;
23     int len=strlen(a);
24     if(len<26)
25     {
26         cout<<"-1"<<endl;
27         return 0;
28     }
29     int flag=0;
30     for(int i=0; i<len; i++)
31     {
32         if(i+25>=len)
33             break;
34         mp.clear();
35         int exm=0;
36         int gg=0;
37         for(int j=1; j<=26; j++)
38         {
39 
40             if(a[i+j-1]=='?')
41                 exm++;
42             else
43             {
44                 if(mp[a[i+j-1]]==0)
45                 {
46                     mp[a[i+j-1]]++;
47                     gg++;
48                 }
49             }
50         }
51         if((exm+gg)==26)
52             flag=1;
53         if(flag)
54         {
55             flag=i+1;
56             break;
57         }
58     }
59     if(flag==0)
60     {
61         cout<<"-1"<<endl;
62         return 0;
63     }
64     flag--;
65     for(int i=flag; i<=flag+25; i++)
66     {
67         if(a[i]=='?')
68         {
69             for(char j='A'; j<='Z'; j++)
70             {
71                 if(mp[j]==0)
72                 {
73                     a[i]=j;
74                     mp[j]=1;
75                     break;
76                 }
77             }
78         }
79     }
80     for(int i=0; i<len; i++){
81         if(a[i]=='?'){
82             a[i]='A';
83         }}
84     for(int i=0; i<len; i++)
85         printf("%c",a[i]);
86     printf("
");
87     return 0;
88 }

ZS the Coder is playing a game. There is a number displayed on the screen and there are two buttons, ' + ' (plus) and ' $\text{[math]}$ ' (square root). Initially, the number 2 is displayed on the screen. There are n + 1 levels in the game and ZS the Coder start at the level 1.

When ZS the Coder is at level k, he can :

Press the ' + ' button. This increases the number on the screen by exactly k. So, if the number on the screen was x, it becomes x + k.
Press the ' $\text{[math]}$ ' button. Let the number on the screen be x. After pressing this button, the number becomes $\text{[math]}$ . After that, ZS the Coder levels up, so his current level becomes k + 1. This button can only be pressed when x is a perfect square, i.e. x = m² for some positive integer m.

Additionally, after each move, if ZS the Coder is at level k, and the number on the screen is m, then m must be a multiple of k. Note that this condition is only checked after performing the press. For example, if ZS the Coder is at level 4 and current number is 100, he presses the ' $\text{[math]}$ ' button and the number turns into 10. Note that at this moment, 10 is not divisible by 4, but this press is still valid, because after it, ZS the Coder is at level 5, and 10 is divisible by 5.

ZS the Coder needs your help in beating the game — he wants to reach level n + 1. In other words, he needs to press the ' $\text{[math]}$ ' button n times. Help him determine the number of times he should press the ' + ' button before pressing the ' $\text{[math]}$ ' button at each level.

Please note that ZS the Coder wants to find just any sequence of presses allowing him to reach level n + 1, but not necessarily a sequence minimizing the number of presses.

Input

The first and only line of the input contains a single integer n (1 ≤ n ≤ 100 000), denoting that ZS the Coder wants to reach level n + 1.

Output

Print n non-negative integers, one per line. i-th of them should be equal to the number of times that ZS the Coder needs to press the ' + ' button before pressing the ' $\text{[math]}$ ' button at level i.

Each number in the output should not exceed 10¹⁸. However, the number on the screen can be greater than 10¹⁸.

It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

Examples

Input

Output

14
16
46

Input

Output

999999999999999998
44500000000

Input

Output

Note

In the first sample case:

On the first level, ZS the Coder pressed the ' + ' button 14 times (and the number on screen is initially 2), so the number became 2 + 14·1 = 16. Then, ZS the Coder pressed the ' $\text{[math]}$ ' button, and the number became $\text{[math]}$ .

After that, on the second level, ZS pressed the ' + ' button 16 times, so the number becomes 4 + 16·2 = 36. Then, ZS pressed the ' $\text{[math]}$ ' button, levelling up and changing the number into $\text{[math]}$ .

After that, on the third level, ZS pressed the ' + ' button 46 times, so the number becomes 6 + 46·3 = 144. Then, ZS pressed the ' $\text{[math]}$ ' button, levelling up and changing the number into $\text{[math]}$ .

Note that 12 is indeed divisible by 4, so ZS the Coder can reach level 4.

Also, note that pressing the ' + ' button 10 times on the third level before levelling up does not work, because the number becomes 6 + 10·3 = 36, and when the ' $\text{[math]}$ ' button is pressed, the number becomes $\text{[math]}$ and ZS the Coder is at Level 4. However, 6 is not divisible by 4 now, so this is not a valid solution.

In the second sample case:

On the first level, ZS the Coder pressed the ' + ' button 999999999999999998 times (and the number on screen is initially 2), so the number became 2 + 999999999999999998·1 = 10¹⁸. Then, ZS the Coder pressed the ' $\text{[math]}$ ' button, and the number became $\text{[math]}$ .

After that, on the second level, ZS pressed the ' + ' button 44500000000 times, so the number becomes 10⁹ + 44500000000·2 = 9·10¹⁰. Then, ZS pressed the ' $\text{[math]}$ ' button, levelling up and changing the number into $\text{[math]}$ .

Note that 300000 is a multiple of 3, so ZS the Coder can reach level 3.

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 //#include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cmath>
11 #include<cstdio>
12 #define ll long long
13 #define mod 1000000007
14 #define PI acos(-1.0)
15 using namespace std;
16 int main()
17 {
18     int n;
19     scanf("%d",&n);
20     cout<<"2"<<endl;
21     for(ll i=2; i<=n; i++)
22     {
23         printf("%I64d
",(i+1)*(i+1)*i-i+1);
24     }
25     return 0;
26 }

Codeforces Round #372 (Div. 2) A B C 水 暴力/模拟 构造

Codeforces Round #372 (Div. 2) A B C 水暴力/模拟构造