明若清溪天下绝歌 缱绻成说，不知该在哪处着墨；一生情深怎奈何世事 徒留斑驳，只一念痴恋成奢。

Suppose you have a special xx-yy-counter. This counter can store some value as a decimal number; at first, the counter has value 00.

The counter performs the following algorithm: it prints its lowest digit and, after that, adds either xx or yy to its value. So all sequences this counter generates are starting from 00. For example, a 44-22-counter can act as follows:

1. it prints 00, and adds 44 to its value, so the current value is 44, and the output is 00;
2. it prints 44, and adds 44 to its value, so the current value is 88, and the output is 0404;
3. it prints 88, and adds 44 to its value, so the current value is 1212, and the output is 048048;
4. it prints 22, and adds 22 to its value, so the current value is 1414, and the output is 04820482;
5. it prints 44, and adds 44 to its value, so the current value is 1818, and the output is 0482404824.

This is only one of the possible outputs; for example, the same counter could generate 02468024680240246802468024 as the output, if we chose to add 22 during each step.

You wrote down a printed sequence from one of such xx-yy-counters. But the sequence was corrupted and several elements from the sequence could be erased.

Now you'd like to recover data you've lost, but you don't even know the type of the counter you used. You have a decimal string ss — the remaining data of the sequence.

For all 0≤x,y<100≤x,y<10, calculate the minimum number of digits you have to insert in the string ss to make it a possible output of the xx-yy-counter. Note that you can't change the order of digits in string ss or erase any of them; only insertions are allowed.

Input

The first line contains a single string ss (1≤|s|≤2⋅1061≤|s|≤2⋅106, si∈{0−9}si∈{0−9}) — the remaining data you have. It's guaranteed that s1=0s1=0.

Output

Print a 10×1010×10 matrix, where the jj-th integer (00-indexed) on the ii-th line (00-indexed too) is equal to the minimum number of digits you have to insert in the string ss to make it a possible output of the ii-jj-counter, or −1−1 if there is no way to do so.

Example

input

Copy

0840

output

Copy

-1 17 7 7 7 -1 2 17 2 7 
17 17 7 5 5 5 2 7 2 7 
7 7 7 4 3 7 1 7 2 5 
7 5 4 7 3 3 2 5 2 3 
7 5 3 3 7 7 1 7 2 7 
-1 5 7 3 7 -1 2 9 2 7 
2 2 1 2 1 2 2 2 0 1 
17 7 7 5 7 9 2 17 2 3 
2 2 2 2 2 2 0 2 2 2 
7 7 5 3 7 7 1 3 2 7 

Note

Let's take, for example, 44-33-counter. One of the possible outcomes the counter could print is 0(4)8(1)4(7)00(4)8(1)4(7)0 (lost elements are in the brackets).

One of the possible outcomes a 22-33-counter could print is 0(35)8(1)4(7)00(35)8(1)4(7)0.

The 66-88-counter could print exactly the string 08400840.

一道交互题（第一次）：

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: https://codeforces.com/blog/entry/45307.

The jury picked an integer xx not less than 00 and not greater than 214−1214−1. You have to guess this integer.

To do so, you may ask no more than 22 queries. Each query should consist of 100100 integer numbers a1a1, a2a2, ..., a100a100 (each integer should be not less than 00 and not greater than 214−1214−1). In response to your query, the jury will pick one integer ii (1≤i≤1001≤i≤100) and tell you the value of ai⊕xai⊕x (the bitwise XOR of aiai and xx). There is an additional constraint on the queries: all 200200 integers you use in the queries should be distinct.

It is guaranteed that the value of xx is fixed beforehand in each test, but the choice of iiin every query may depend on the integers you send.

Output

To give the answer, your program should print one line !! xx with a line break in the end. After that, it should flush the output and terminate gracefully.

Interaction

Before giving the answer, you may submit no more than 22 queries. To ask a query, print one line in the following format: ?? a1a1 a2a2 ... a100a100, where every ajaj should be an integer from the range [0,214−1][0,214−1]. The line should be ended with a line break character. After submitting a query, flush the output and read the answer to your query — the value of ai⊕xai⊕x for some i∈[1,100]i∈[1,100]. No integer can be used in queries more than once.

If you submit an incorrect query (or ask more than 22 queries), the answer to it will be one integer −1−1. After receiving such an answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer".

Example

input

Copy

0
32

output

Copy

? 3 5 6
? 32 24 37
! 5

Note

The example of interaction is not correct — you should sumbit exactly 100100 integers in each query. Everything else is correct.

Hacks are forbidden in this problem.

1.fflush(stdin)刷新标准输入缓冲区，把输入缓冲区里的东西丢弃
2.fflush(stdout)刷新标准输出缓冲区，把输出缓冲区里的东西打印到标准输出设备上

一般这种题目可以理解为输出做输入，输入做输出。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int jg,x;
int main()
{
    printf("? ");
    for(int i=1; i<=100; i++)
    {
        if(i==100)
            printf("%d\n",i);
        else
            printf("%d ",i);
    }
    fflush(stdout);
    scanf("%d",&x);
    for(int i=7;i<=14;i++)
        jg|=((1<<i)&x);
    printf("? ");
    for(int i=1;i<=100;i++)
    {
        if(i==100)
            printf("%d\n",i<<7);
        else
            printf("%d ",i<<7);
    }
    fflush(stdout);
    scanf("%d",&x);
    for(int i=0;i<=6;i++)
        jg|=((1<<i)&x);
    printf("! %d\n",jg);
    fflush(stdout);
    return 0;
}

额外的交互入门题：

This is an interactive problem. In the output section below you will see the information about flushing the output.

Bear Limak thinks of some hidden number — an integer from interval [2, 100]. Your task is to say if the hidden number is prime or composite.

Integer x > 1 is called prime if it has exactly two distinct divisors, 1 and x. If integer x > 1 is not prime, it's called composite.

You can ask up to 20 queries about divisors of the hidden number. In each query you should print an integer from interval [2, 100]. The system will answer "yes" if your integer is a divisor of the hidden number. Otherwise, the answer will be "no".

For example, if the hidden number is 14 then the system will answer "yes" only if you print 2, 7 or 14.

When you are done asking queries, print "prime" or "composite" and terminate your program.

You will get the Wrong Answer verdict if you ask more than 20 queries, or if you print an integer not from the range [2, 100]. Also, you will get the Wrong Answer verdict if the printed answer isn't correct.

You will get the Idleness Limit Exceeded verdict if you don't print anything (but you should) or if you forget about flushing the output (more info below).

Input

After each query you should read one string from the input. It will be "yes" if the printed integer is a divisor of the hidden number, and "no" otherwise.

Output

Up to 20 times you can ask a query — print an integer from interval [2, 100] in one line. You have to both print the end-of-line character and flush the output. After flushing you should read a response from the input.

In any moment you can print the answer "prime" or "composite" (without the quotes). After that, flush the output and terminate your program.

To flush you can use (just after printing an integer and end-of-line):

• fflush(stdout) in C++;
• System.out.flush() in Java;
• stdout.flush() in Python;
• flush(output) in Pascal;
• See the documentation for other languages.

Hacking. To hack someone, as the input you should print the hidden number — one integer from the interval [2, 100]. Of course, his/her solution won't be able to read the hidden number from the input.

Examples

input

Copy

yes
no
yes

output

Copy

2
80
5
composite

input

Copy

no
yes
no
no
no

output

Copy

58
59
78
78
2
prime

Note

The hidden number in the first query is 30. In a table below you can see a better form of the provided example of the communication process.

The hidden number is divisible by both 2 and 5. Thus, it must be composite. Note that it isn't necessary to know the exact value of the hidden number. In this test, the hidden number is 30.

59 is a divisor of the hidden number. In the interval [2, 100] there is only one number with this divisor. The hidden number must be 59, which is prime. Note that the answer is known even after the second query and you could print it then and terminate. Though, it isn't forbidden to ask unnecessary queries (unless you exceed the limit of 20 queries).

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int prime[30]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
int main(){
    int ct=0;
    for(int i=0;i<19;i++){
        cout<<prime[i]<<endl;
        fflush(stdout);
        string ss;
        cin>>ss;
        if(ss=="yes")
            ct++;
    }
    if(ct>1)
        cout<<"composite"<<endl;
    else
        cout<<"prime"<<endl;
    fflush(stdout);
    return 0;
}

There are nn boxers, the weight of the ii-th boxer is aiai. Each of them can change the weight by no more than 11 before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.

It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers' weights in the team are different (i.e. unique).

Write a program that for given current values ​aiai will find the maximum possible number of boxers in a team.

It is possible that after some change the weight of some boxer is 150001150001 (but no more).

Input

The first line contains an integer nn (1≤n≤1500001≤n≤150000) — the number of boxers. The next line contains nn integers a1,a2,…,ana1,a2,…,an, where aiai (1≤ai≤1500001≤ai≤150000) is the weight of the ii-th boxer.

Output

Print a single integer — the maximum possible number of people in a team.

Examples

input

Copy

4
3 2 4 1

output

Copy

4

input

Copy

6
1 1 1 4 4 4

output

Copy

5

Note

In the first example, boxers should not change their weights — you can just make a team out of all of them.

In the second example, one boxer with a weight of 11 can be increased by one (get the weight of 22), one boxer with a weight of 44 can be reduced by one, and the other can be increased by one (resulting the boxers with a weight of 33 and 55, respectively). Thus, you can get a team consisting of boxers with weights of 5,4,3,2,15,4,3,2,1.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int ct,n,a[150010],fg[10]= {1,0,-1},ls,jg;
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    ct=a[n-1]+2;
    for(int i = n-1 ; i >= 0; i--)
    {
        int tt = -1;
        for(int j = 0; j < 3; j++)
        {
            ls = a[i] + fg[j];
            if(ls > 0 && ls < ct)
            {
                tt = ls;
                ct = tt;
                break;
            }
        }
        if(tt == -1)
            continue;
        jg++;
    }
    printf("%d\n",jg);
    return 0;
}