cf----2019-08-28（H. BerOS File Suggestion，Garbage Disposal， Debate）

人群淹没，你我不及诉说。一声雁过，往事如昨。只望离别不多，再赏盛世烟火。

Polycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature.

There are nn files on hard drive and their names are f1,f2,…,fnf1,f2,…,fn. Any file name contains between 11 and 88 characters, inclusive. All file names are unique.

The file suggestion feature handles queries, each represented by a string ss. For each query ss it should count number of files containing ssas a substring (i.e. some continuous segment of characters in a file name equals ss) and suggest any such file name.

For example, if file names are "read.me", "hosts", "ops", and "beros.18", and the query is "os", the number of matched files is 22(two file names contain "os" as a substring) and suggested file name can be either "hosts" or "beros.18".

Input

The first line of the input contains integer nn (1≤n≤100001≤n≤10000) — the total number of files.

The following nn lines contain file names, one per line. The ii-th line contains fifi — the name of the ii-th file. Each file name contains between 11 and 88 characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters ('.'). Any sequence of valid characters can be a file name (for example, in BerOS ".", ".." and "..." are valid file names). All file names are unique.

The following line contains integer qq (1≤q≤500001≤q≤50000) — the total number of queries.

The following qq lines contain queries s1,s2,…,sqs1,s2,…,sq, one per line. Each sjsj has length between 11 and 88 characters, inclusive. It contains only lowercase Latin letters, digits and dot characters ('.').

Output

Print qq lines, one per query. The jj-th line should contain the response on the jj-th query — two values cjcj and tjtj, where

• cjcj is the number of matched files for the jj-th query,
• tjtj is the name of any file matched by the jj-th query. If there is no such file, print a single character '-' instead. If there are multiple matched files, print any.

Example

input

Copy

4
test
contests
test.
.test
6
ts
.
st.
.test
contes.
st

output

Copy

1 contests
2 .test
1 test.
1 .test
0 -
4 test.

#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;
map<string,set<int> >mp;
int N,K;
string s[10010],ss,tmp;
int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>s[i];
        int cd=s[i].size();
        for(int j=1;j<=cd;j++){
            for(int k=0;k+j<=cd;k++){
                tmp=s[i].substr(k,j);//获得字符串s中从第k位开始的长度为j的字符串
                mp[tmp].insert(i);
            }
        }
    }
    cin>>K;
    while(K--){
        cin>>ss;
        if(!mp.count(ss))
            cout<<"0 -"<<endl;
        else
            cout<<mp[ss].size()<<' '<<s[*mp[ss].begin()]<<endl;
    }
    return 0;
}

Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next nn days Vasya knows aiai — number of units of garbage he will produce on the ii-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to kk units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given nn days. No garbage should be left after the nn-th day.

Input

The first line of the input contains two integers nn and kk (1≤n≤2⋅105,1≤k≤1091≤n≤2⋅105,1≤k≤109) — number of days to consider and bag's capacity. The second line contains nn space separated integers aiai (0≤ai≤1090≤ai≤109) — the number of units of garbage produced on the ii-th day.

Output

Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the nn-th day. In a day it is allowed to compose and drop multiple bags.

Examples

input

Copy

3 2
3 2 1

output

Copy

3

input

Copy

5 1
1000000000 1000000000 1000000000 1000000000 1000000000

output

Copy

5000000000

input

Copy

3 2
1 0 1

output

Copy

2

input

Copy

4 4
2 8 4 1

output

Copy

4

#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 n,k,a,ct;
ll jg;
int main()
{
    cin>>n>>k;
    for(int i = 0; i < n; i++)
    {
        scanf("%d",&a);
        if(ct!=0)
        {
            ct += a;
            if(ct >= k)
            {
                jg += ct / k;
                ct = ct % k;
            }
            else
            {
                ct = 0;
                jg++;
            }
        }
        else
        {
            ct += a;
            if(ct >= k)
            {
                jg += (ll)(ct / k);
                ct = ct % k;
            }
        }
    }
    if(ct!=0)
        jg++;
    printf("%lld\n",jg);
    return 0;
}

Elections in Berland are coming. There are only two candidates — Alice and Bob.

The main Berland TV channel plans to show political debates. There are nn people who want to take part in the debate as a spectator. Each person is described by their influence and political views. There are four kinds of political views:

• supporting none of candidates (this kind is denoted as "00"),
• supporting Alice but not Bob (this kind is denoted as "10"),
• supporting Bob but not Alice (this kind is denoted as "01"),
• supporting both candidates (this kind is denoted as "11").

The direction of the TV channel wants to invite some of these people to the debate. The set of invited spectators should satisfy three conditions:

• at least half of spectators support Alice (i.e. 2⋅a≥m2⋅a≥m, where aa is number of spectators supporting Alice and mm is the total number of spectators),
• at least half of spectators support Bob (i.e. 2⋅b≥m2⋅b≥m, where bb is number of spectators supporting Bob and mm is the total number of spectators),
• the total influence of spectators is maximal possible.

Help the TV channel direction to select such non-empty set of spectators, or tell that this is impossible.

Input

The first line contains integer nn (1≤n≤4⋅1051≤n≤4⋅105) — the number of people who want to take part in the debate as a spectator.

These people are described on the next nn lines. Each line describes a single person and contains the string sisi and integer aiai separated by space (1≤ai≤50001≤ai≤5000), where sisi denotes person's political views (possible values — "00", "10", "01", "11") and aiai — the influence of the ii-th person.

Output

Print a single integer — maximal possible total influence of a set of spectators so that at least half of them support Alice and at least half of them support Bob. If it is impossible print 0 instead.

Examples

input

Copy

6
11 6
10 4
01 3
00 3
00 7
00 9

output

Copy

22

input

Copy

5
11 1
01 1
00 100
10 1
01 1

output

Copy

103

input

Copy

6
11 19
10 22
00 18
00 29
11 29
10 28

output

Copy

105

input

Copy

3
00 5000
00 5000
00 5000

output

Copy

0

Note

In the first example 44 spectators can be invited to maximize total influence: 11, 22, 33 and 66. Their political views are: "11", "10", "01" and "00". So in total 22 out of 44 spectators support Alice and 22 out of 44 spectators support Bob. The total influence is 6+4+3+9=226+4+3+9=22.

In the second example the direction can select all the people except the 55-th person.

In the third example the direction can select people with indices: 11, 44, 55 and 66.

In the fourth example it is impossible to select any non-empty set of spectators.

#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 N,jg;
struct node
{
    int s;
    int a;
} s1[1000010],s2[1000010],s3[1000010];
int cmp(node x,node y)
{
    return x.a>y.a;
}
int main()
{
    cin>>N;
    int ct0=0,ct1=0,ct2=0,ct3=0;
    for(int i=0; i<N; i++)
    {
        int ss,aa;
        cin>>ss>>aa;
        if(ss==11)
        {
            jg+=aa;
            ct0++;
        }
        if(ss==10)
        {
            s1[ct1].s=ss;
            s1[ct1].a=aa;
            ct1++;
        }
        if(ss==1)
        {
            s2[ct2].s=ss;
            s2[ct2].a=aa;
            ct2++;
        }
        if(ss==0)
        {
            s3[ct3].s=ss;
            s3[ct3].a=aa;
            ct3++;
        }
    }
    sort(s1,s1+ct1,cmp);
    sort(s2,s2+ct2,cmp);
    int mi=min(ct2,ct1);
    for(int i=0; i<mi; i++)
        jg+=s1[i].a+s2[i].a;
    int all=(ct0+mi)*2;
    int k=all-ct0-mi*2;
    if(ct1>ct2)
    {
        for(int i=mi; i<ct1; i++)
            s3[ct3++]=s1[i];
    }
    else
    {
        for(int i=mi; i<ct2; i++)
            s3[ct3++]=s2[i];
    }
    sort(s3,s3+ct3,cmp);
    for(int i=0; i<k; i++)
        jg+=s3[i].a;
    cout<<jg<<endl;
    return 0;
}