Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than k other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim's coins.

Now each knight ponders: how many coins he can have if only he kills other knights?

You should answer this question for each knight.

Input

The first line contains two integers n and k (1≤n≤105,0≤k≤min(n−1,10)) — the number of knights and the number k from the statement.

The second line contains n integers p1,p2,…,pn (1≤pi≤109) — powers of the knights. All pi are distinct.

The third line contains n integers c1,c2,…,cn (0≤ci≤109) — the number of coins each knight has.

Output

Print n integers — the maximum number of coins each knight can have it only he kills other knights.

Examples

Input

4 2

4 5 9 7

1 2 11 33

Output

1 3 46 36

Input

5 1

1 2 3 4 5

1 2 3 4 5

Output

1 3 5 7 9

Input

1 0

2

3

Output

3

Note

Consider the first example.

The first knight is the weakest, so he can't kill anyone. That leaves him with the only coin he initially has.

The second knight can kill the first knight and add his coin to his own two.

The third knight is the strongest, but he can't kill more than k=2 other knights. It is optimal to kill the second and the fourth knights: 2+11+33=46.

The fourth knight should kill the first and the second knights: 33+1+2=36.

In the second example the first knight can't kill anyone, while all the others should kill the one with the index less by one than their own.

In the third example there is only one knight, so he can't kill anyone.

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long n,k;

    cin>>n>>k;

    long long a[n+5],b[n+5],c[n+5]={0};

    for(long long i=0;i<n;i++)

    {

        cin>>a[i];

    }

    for(long long i=0;i<n;i++)cin>>b[i];

    for(long long i=0;i<n;i++)

    {

        long long p=0;

        for(long long j=0;j<n;j++)

        {

            if(a[i]>a[j])

            {

                c[p]=b[j];

                ++p;

            }

        }

        sort(c,c+p);

        int ct=0,num=b[i];

        for(long long w=p-1;w>=0;w--)

        {

            if(ct<k)

            {

                num+=c[w];

                ++ct;

            }

        }

        if(i==0)cout<<num;

        else cout<<" "<<num;

    }

}

You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect.

The interior of the square is considered to be part of the square, i.e. if one square is completely inside another, they intersect. If the two squares only share one common point, they are also considered to intersect.

Input

The input data consists of two lines, one for each square, both containing 4 pairs of integers. Each pair represents coordinates of one vertex of the square. Coordinates within each line are either in clockwise or counterclockwise order.

The first line contains the coordinates of the square with sides parallel to the coordinate axes, the second line contains the coordinates of the square at 45 degrees.

All the values are integer and between −100 and 100.

Output

Print "Yes" if squares intersect, otherwise print "No".

You can print each letter in any case (upper or lower).

Examples

Input

0 0 6 0 6 6 0 6

1 3 3 5 5 3 3 1

Output

YES

Input

0 0 6 0 6 6 0 6

7 3 9 5 11 3 9 1

Output

NO

Input

6 0 6 6 0 6 0 0

7 4 4 7 7 10 10 7

Output

YES

Note

In the first example the second square lies entirely within the first square, so they do intersect.

In the second sample squares do not have any points in common.

Here are images corresponding to the samples: