Codeforces Round #451 (Div. 2)

Vasya has a non-negative integer n. He wants to round it to nearest integer, which ends up with 0. If n already ends up with 0, Vasya considers it already rounded.

For example, if n = 4722 answer is 4720. If n = 5 Vasya can round it to 0 or to 10. Both ways are correct.

For given n find out to which integer will Vasya round it.

Input

The first line contains single integer n (0 ≤ n ≤ 109) — number that Vasya has.

Output

Print result of rounding n. Pay attention that in some cases answer isn't unique. In that case print any correct answer.

Examples

input

output

input

output

input

1000000000

output

1000000000

input

output

Note

In the first example n = 5. Nearest integers, that ends up with zero are 0 and 10. Any of these answers is correct, so you can print 0 or 10.

四舍五入，没有看完题就在打，错了啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    cout<<(n/10+(n%10>=5))*10;
    return 0;
}

Vasya has n burles. One bottle of Ber-Cola costs a burles and one Bars bar costs b burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number of Bars bars.

Find out if it's possible to buy some amount of bottles of Ber-Cola and Bars bars and spend exactly n burles.

In other words, you should find two non-negative integers x and y such that Vasya can buy x bottles of Ber-Cola and y Bars bars and x·a + y·b = n or tell that it's impossible.

Input

First line contains single integer n (1 ≤ n ≤ 10 000 000) — amount of money, that Vasya has.

Second line contains single integer a (1 ≤ a ≤ 10 000 000) — cost of one bottle of Ber-Cola.

Third line contains single integer b (1 ≤ b ≤ 10 000 000) — cost of one Bars bar.

Output

If Vasya can't buy Bars and Ber-Cola in such a way to spend exactly n burles print «NO» (without quotes).

Otherwise in first line print «YES» (without quotes). In second line print two non-negative integers x and y — number of bottles of Ber-Cola and number of Bars bars Vasya should buy in order to spend exactly n burles, i.e. x·a + y·b = n. If there are multiple answers print any of them.

Any of numbers x and y can be equal 0.

Examples

input

7
2
3

output

YES
2 1

input

100
25
10

output

YES
0 10

input

15
4
8

output

NO

input

9960594
2551
2557

output

YES
1951 1949

Note

In first example Vasya can buy two bottles of Ber-Cola and one Bars bar. He will spend exactly 2·2 + 1·3 = 7 burles.

In second example Vasya can spend exactly n burles multiple ways:

buy two bottles of Ber-Cola and five Bars bars;
buy four bottles of Ber-Cola and don't buy Bars bars;
don't buy Ber-Cola and buy 10 Bars bars.

In third example it's impossible to but Ber-Cola and Bars bars in order to spend exactly n burles.

直接for暴力枚举啊

本来在想扩欧的事情，ax+by=gcd(a,b)，这样的话可以直接化为扩欧，然后解出a,b，然后扩大相应倍数，然后再给他都加到非负数就可以了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,a,b;
    cin>>n>>a>>b;
    for(int i=0; i<=n/a; i++)
    {
        if((n-(a*i))%b==0)
        {
            printf("YES
");
            printf("%d %d",i,(n-(a*i))/b);
            return 0;
        }
    }
    printf("NO");
    return 0;
}

exgcd的实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(!b)
    {
        d=a;
        x=1;
        y=0;
        return ;
    }
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}
int main()
{
    ll n,a,b;
    scanf("%lld %lld %lld",&n,&a,&b);
    ll d,x,y;
    exgcd(a,b,d,x,y);
    if(n%d!=0)
    {
        puts("NO");
        return 0;
    }
    ll ta=a/d,tb=b/d;
    x*=(n/d),y*=(n/d);
    ll p=(x%tb+tb)%tb;
    ll tl=abs(x-p)/tb;
    if(x>p)y+=tl*ta;
    else y-=tl*ta;
    if(y>=0)printf("YES
%lld %lld
",p,y);
    else puts("NO");
    return 0;
}

Vasya has several phone books, in which he recorded the telephone numbers of his friends. Each of his friends can have one or several phone numbers.

Vasya decided to organize information about the phone numbers of friends. You will be given n strings — all entries from Vasya's phone books. Each entry starts with a friend's name. Then follows the number of phone numbers in the current entry, and then the phone numbers themselves. It is possible that several identical phones are recorded in the same record.

Vasya also believes that if the phone number a is a suffix of the phone number b (that is, the number b ends up with a), and both numbers are written by Vasya as the phone numbers of the same person, then a is recorded without the city code and it should not be taken into account.

The task is to print organized information about the phone numbers of Vasya's friends. It is possible that two different people have the same number. If one person has two numbers x and y, and x is a suffix of y (that is, y ends in x), then you shouldn't print number x. If the number of a friend in the Vasya's phone books is recorded several times in the same format, it is necessary to take it into account exactly once.

Read the examples to understand statement and format of the output better.

Input

First line contains the integer n (1 ≤ n ≤ 20) — number of entries in Vasya's phone books.

The following n lines are followed by descriptions of the records in the format described in statement. Names of Vasya's friends are non-empty strings whose length does not exceed 10. They consists only of lowercase English letters. Number of phone numbers in one entry is not less than 1 is not more than 10. The telephone numbers consist of digits only. If you represent a phone number as a string, then its length will be in range from 1 to 10. Phone numbers can contain leading zeros.

Output

Print out the ordered information about the phone numbers of Vasya's friends. First output m — number of friends that are found in Vasya's phone books.

The following m lines must contain entries in the following format "name number_of_phone_numbers phone_numbers". Phone numbers should be separated by a space. Each record must contain all the phone numbers of current friend.

Entries can be displayed in arbitrary order, phone numbers for one record can also be printed in arbitrary order.

Examples

input

2
ivan 1 00123
masha 1 00123

output

2
masha 1 00123 
ivan 1 00123

input

3
karl 2 612 12
petr 1 12
katya 1 612

output

3
katya 1 612 
petr 1 12 
karl 1 612

input

4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789

output

2
dasha 2 23 789 
ivan 4 789 123 2 456

裸的字典树，不过暴力应该也可以过的

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int nxt[N][10],num[N];
int tot;
string s;
char ss[1005];
map<string,int>M;
int newnode()
{
    tot++;
    memset(nxt[tot],0,sizeof(int)*10);
    return tot;
}
void Insert(char *s,int rt)
{
    num[rt]++;
    if(!(*s))return;
    if(!nxt[rt][*s-'0'])nxt[rt][*s-'0']=newnode();
    Insert(s+1,nxt[rt][*s-'0']);
}
int la(int rt)
{
    if (rt==0)return 0;
    int f=0;
    for (int i=0; i<10; i++)
        f+=la(nxt[rt][i]);
    return f+(!f);
}
void lb(int rt,char *s)
{
    int f=0;
    for (int i=0; i<10; i++)
        if (nxt[rt][i])f=1,*(s)=i+'0',lb(nxt[rt][i],s-1);
    if (!f)printf(" %s",s+1);
    return ;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++)
    {
        cin>>s;
        if(!M.count(s))M[s]=newnode();
        int rt=M[s];
        int k;
        scanf("%d",&k);
        while (k--)
        {
            cin>>s;
            reverse(s.begin(),s.end());
            strcpy(ss,s.c_str());
            Insert(ss,rt);
        }
    }
    printf("%d
",M.size());
    for (auto X:M)
    {
        cout<<X.first<<" ";
        int rt=X.second;
        printf(" %d",la(rt));
        lb(rt,ss+6000);
        puts("");
    }
    return 0;
}

Ann and Borya have n piles with candies and n is even number. There are ai candies in pile with number i.

Ann likes numbers which are square of some integer and Borya doesn't like numbers which are square of any integer. During one move guys can select some pile with candies and add one candy to it (this candy is new and doesn't belong to any other pile) or remove one candy (if there is at least one candy in this pile).

Find out minimal number of moves that is required to make exactly n / 2 piles contain number of candies that is a square of some integer and exactly n / 2 piles contain number of candies that is not a square of any integer.

Input

First line contains one even integer n (2 ≤ n ≤ 200 000) — number of piles with candies.

Second line contains sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 109) — amounts of candies in each pile.

Output

Output minimal number of steps required to make exactly n / 2 piles contain number of candies that is a square of some integer and exactly n / 2 piles contain number of candies that is not a square of any integer. If condition is already satisfied output 0.

Examples

input

4
12 14 30 4

output

input

6
0 0 0 0 0 0

output

input

6
120 110 23 34 25 45

output

input

10
121 56 78 81 45 100 1 0 54 78

output

Note

In first example you can satisfy condition in two moves. During each move you should add one candy to second pile. After it size of second pile becomes 16. After that Borya and Ann will have two piles with number of candies which is a square of integer (second and fourth pile) and two piles with number of candies which is not a square of any integer (first and third pile).

In second example you should add two candies to any three piles.

直接map以下就可以了啊，当时竟然没有做这个题目，亏大发了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll n,ans;
const int N=2e5+5;
pair<int,int>a[N];
int find(int x)
{
    int y=sqrt(x);
    int a=x-y*y,b=(++y*y)-x;
    return min(a,b);
}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i].se),a[i].fi=find(a[i].se);
    sort(a,a+n);
    int f=n/2;
    for(int i=0; i<f; i++)
        ans+=a[i].fi+((!a[f+i].fi)+(!a[f+i].fi&&!a[f+i].se));
    cout<<ans;
}