Codeforces Round #378 (Div. 2) A B C D 施工中

A. Grasshopper And the String

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum jump ability he should have in order to be able to reach the far end of the string, jumping only on vowels of the English alphabet. Jump ability is the maximum possible length of his jump.

Formally, consider that at the begginning the Grasshopper is located directly in front of the leftmost character of the string. His goal is to reach the position right after the rightmost character of the string. In one jump the Grasshopper could jump to the right any distance from 1 to the value of his jump ability.

The picture corresponds to the first example.

The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'.

Input

The first line contains non-empty string consisting of capital English letters. It is guaranteed that the length of the string does not exceed 100.

Output

Print single integer a — the minimum jump ability of the Grasshopper (in the number of symbols) that is needed to overcome the given string, jumping only on vowels.

Examples

Input

ABABBBACFEYUKOTT

Output

4

Input

AAA

Output

1

题意：
题解：

/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^    ^ ^
 O      O
******************************/
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define  A first
#define B second
const int mod=1000000007;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef __int64 ll;
const ll MOD=1000000007;
const int INF=1000000010;
const ll MAX=1ll<<55;
const double eps=1e-14;
const double inf=~0u>>1;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int n;
char a[105];
int main()
{
    cin>>a;
    int maxn=0;
    int len=strlen(a);
    for(int i=0; i<len; i++)
    {
        if(a[i]=='A'||a[i]=='E'||a[i]=='I'||a[i]=='O'||a[i]=='U'||a[i]=='Y')
        {
            maxn=i+1;
            break;
        }
    }
    for(int i=0; i<len; i++)
    {
        int j=i;
        if(a[i]=='A'||a[i]=='E'||a[i]=='I'||a[i]=='O'||a[i]=='U'||a[i]=='Y')
        {

            for( j=i+1; j<len; j++)
            {
                if(a[j]=='A'||a[j]=='E'||a[j]=='I'||a[j]=='O'||a[j]=='U'||a[j]=='Y')
                {
                    maxn=max(maxn,j-i);
                    break;
                }
            }
        }
    }
    for(int i=len-1; i>=0; i--)
    {
        if(a[i]=='A'||a[i]=='E'||a[i]=='I'||a[i]=='O'||a[i]=='U'||a[i]=='Y')
        {
            maxn=max(maxn,len-i);
            break;
        }
    }
    if(maxn==0)
        printf("%d
",len+1);
    else
        printf("%d
",maxn);
    return 0;
}

B. Parade

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Very soon there will be a parade of victory over alien invaders in Berland. Unfortunately, all soldiers died in the war and now the army consists of entirely new recruits, many of whom do not even know from which leg they should begin to march. The civilian population also poorly understands from which leg recruits begin to march, so it is only important how many soldiers march in step.

There will be n columns participating in the parade, the i-th column consists of l_i soldiers, who start to march from left leg, and r_i soldiers, who start to march from right leg.

The beauty of the parade is calculated by the following formula: if L is the total number of soldiers on the parade who start to march from the left leg, and R is the total number of soldiers on the parade who start to march from the right leg, so the beauty will equal |L - R|.

No more than once you can choose one column and tell all the soldiers in this column to switch starting leg, i.e. everyone in this columns who starts the march from left leg will now start it from right leg, and vice versa. Formally, you can pick no more than one index i and swap values l_i and r_i.

Find the index of the column, such that switching the starting leg for soldiers in it will maximize the the beauty of the parade, or determine, that no such operation can increase the current beauty.

Input

The first line contains single integer n (1 ≤ n ≤ 10⁵) — the number of columns.

The next n lines contain the pairs of integers l_i and r_i (1 ≤ l_i, r_i ≤ 500) — the number of soldiers in the i-th column which start to march from the left or the right leg respectively.

Output

Print single integer k — the number of the column in which soldiers need to change the leg from which they start to march, or 0 if the maximum beauty is already reached.

Consider that columns are numbered from 1 to n in the order they are given in the input data.

If there are several answers, print any of them.

Examples

Input

3
5 6
8 9
10 3

Output

3

Input

2
6 5
5 6

Output

1

Input

6
5 9
1 3
4 8
4 5
23 54
12 32

Output

0

Note

In the first example if you don't give the order to change the leg, the number of soldiers, who start to march from the left leg, would equal 5 + 8 + 10 = 23, and from the right leg — 6 + 9 + 3 = 18. In this case the beauty of the parade will equal |23 - 18| = 5.

If you give the order to change the leg to the third column, so the number of soldiers, who march from the left leg, will equal 5 + 8 + 3 = 16, and who march from the right leg — 6 + 9 + 10 = 25. In this case the beauty equals |16 - 25| = 9.

It is impossible to reach greater beauty by giving another orders. Thus, the maximum beauty that can be achieved is 9.

/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^    ^ ^
 O      O
******************************/
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define  A first
#define B second
const int mod=1000000007;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef __int64 ll;
const ll MOD=1000000007;
const int INF=1000000010;
const ll MAX=1ll<<55;
const double eps=1e-14;
const double inf=~0u>>1;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int n;
struct  node
{
    ll l,r;
    ll pos;
    ll w;
}N[100005];
bool cmp(struct node aa,struct node bb)
{
    return aa.w>bb.w;
}
int main()
{
    scanf("%d",&n);
    ll aa=0,bb=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%I64d %I64d",&N[i].l,&N[i].r);
        N[i].pos=i;
        aa+=N[i].l;
        bb+=N[i].r;
    }
    ll exm=aa-bb;
    for(int i=1; i<=n; i++)
    {
            ll zha=N[i].l-N[i].r;
            ll zhong;
            zha=exm-zha*2;
            if(exm<0)
                zhong=-exm;
            else
                zhong=exm;
            if(zha<0)
                zha=-zha;
            N[i].w=zha-zhong;
    }
    sort(N+1,N+1+n,cmp);
    if(N[1].w<0)
    printf("0
");
    else
    printf("%I64d
",N[1].pos);
    return 0;
}

C. Epidemic in Monstropolis

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There was an epidemic in Monstropolis and all monsters became sick. To recover, all monsters lined up in queue for an appointment to the only doctor in the city.

Soon, monsters became hungry and began to eat each other.

One monster can eat other monster if its weight is strictly greater than the weight of the monster being eaten, and they stand in the queue next to each other. Monsters eat each other instantly. There are no monsters which are being eaten at the same moment. After the monster A eats the monster B, the weight of the monster A increases by the weight of the eaten monster B. In result of such eating the length of the queue decreases by one, all monsters after the eaten one step forward so that there is no empty places in the queue again. A monster can eat several monsters one after another. Initially there were n monsters in the queue, the i-th of which had weight a_i.

For example, if weights are [1, 2, 2, 2, 1, 2] (in order of queue, monsters are numbered from 1 to 6 from left to right) then some of the options are:

1. the first monster can't eat the second monster because a₁ = 1 is not greater than a₂ = 2;
2. the second monster can't eat the third monster because a₂ = 2 is not greater than a₃ = 2;
3. the second monster can't eat the fifth monster because they are not neighbors;
4. the second monster can eat the first monster, the queue will be transformed to [3, 2, 2, 1, 2].

After some time, someone said a good joke and all monsters recovered. At that moment there were k (k ≤ n) monsters in the queue, the j-th of which had weight b_j. Both sequences (a and b) contain the weights of the monsters in the order from the first to the last.

You are required to provide one of the possible orders of eating monsters which led to the current queue, or to determine that this could not happen. Assume that the doctor didn't make any appointments while monsters were eating each other.

Input

The first line contains single integer n (1 ≤ n ≤ 500) — the number of monsters in the initial queue.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶) — the initial weights of the monsters.

The third line contains single integer k (1 ≤ k ≤ n) — the number of monsters in the queue after the joke.

The fourth line contains k integers b₁, b₂, ..., b_k (1 ≤ b_j ≤ 5·10⁸) — the weights of the monsters after the joke.

Monsters are listed in the order from the beginning of the queue to the end.

Output

In case if no actions could lead to the final queue, print "NO" (without quotes) in the only line.

Otherwise print "YES" (without quotes) in the first line. In the next n - k lines print actions in the chronological order. In each line print x — the index number of the monster in the current queue which eats and, separated by space, the symbol 'L' if the monster which stays the x-th in the queue eats the monster in front of him, or 'R' if the monster which stays the x-th in the queue eats the monster behind him. After each eating the queue is enumerated again.

When one monster eats another the queue decreases. If there are several answers, print any of them.

Examples

Input

6
1 2 2 2 1 2
2
5 5

Output

YES
2 L
1 R
4 L
3 L

Input

5
1 2 3 4 5
1
15

Output

YES
5 L
4 L
3 L
2 L

Input

5
1 1 1 3 3
3
2 1 6

Output

NO

Note

In the first example, initially there were n = 6 monsters, their weights are [1, 2, 2, 2, 1, 2] (in order of queue from the first monster to the last monster). The final queue should be [5, 5]. The following sequence of eatings leads to the final queue:

• the second monster eats the monster to the left (i.e. the first monster), queue becomes [3, 2, 2, 1, 2];
• the first monster (note, it was the second on the previous step) eats the monster to the right (i.e. the second monster), queue becomes [5, 2, 1, 2];
• the fourth monster eats the mosnter to the left (i.e. the third monster), queue becomes [5, 2, 3];
• the finally, the third monster eats the monster to the left (i.e. the second monster), queue becomes [5, 5].

Note that for each step the output contains numbers of the monsters in their current order in the queue.

D. Kostya the Sculptor

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kostya is a genial sculptor, he has an idea: to carve a marble sculpture in the shape of a sphere. Kostya has a friend Zahar who works at a career. Zahar knows about Kostya's idea and wants to present him a rectangular parallelepiped of marble from which he can carve the sphere.

Zahar has n stones which are rectangular parallelepipeds. The edges sizes of the i-th of them are a_i, b_i and c_i. He can take no more than two stones and present them to Kostya.

If Zahar takes two stones, he should glue them together on one of the faces in order to get a new piece of rectangular parallelepiped of marble. Thus, it is possible to glue a pair of stones together if and only if two faces on which they are glued together match as rectangles. In such gluing it is allowed to rotate and flip the stones in any way.

Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar.

Input

The first line contains the integer n (1 ≤ n ≤ 10⁵).

n lines follow, in the i-th of which there are three integers a_i, b_i and c_i (1 ≤ a_i, b_i, c_i ≤ 10⁹) — the lengths of edges of the i-th stone. Note, that two stones may have exactly the same sizes, but they still will be considered two different stones.

Output

In the first line print k (1 ≤ k ≤ 2) the number of stones which Zahar has chosen. In the second line print k distinct integers from 1 to n — the numbers of stones which Zahar needs to choose. Consider that stones are numbered from 1 to n in the order as they are given in the input data.

You can print the stones in arbitrary order. If there are several answers print any of them.

Examples

Input

6
5 5 5
3 2 4
1 4 1
2 1 3
3 2 4
3 3 4

Output

1
1

Input

7
10 7 8
5 10 3
4 2 6
5 5 5
10 2 8
4 2 1
7 7 7

Output

2
1 5

Note

In the first example we can connect the pairs of stones:

• 2 and 4, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1
• 2 and 5, the size of the parallelepiped: 3 × 2 × 8 or 6 × 2 × 4 or 3 × 4 × 4, the radius of the inscribed sphere 1, or 1, or 1.5 respectively.
• 2 and 6, the size of the parallelepiped: 3 × 5 × 4, the radius of the inscribed sphere 1.5
• 4 and 5, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1
• 5 and 6, the size of the parallelepiped: 3 × 4 × 5, the radius of the inscribed sphere 1.5

Or take only one stone:

• 1 the size of the parallelepiped: 5 × 5 × 5, the radius of the inscribed sphere 2.5
• 2 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1
• 3 the size of the parallelepiped: 1 × 4 × 1, the radius of the inscribed sphere 0.5
• 4 the size of the parallelepiped: 2 × 1 × 3, the radius of the inscribed sphere 0.5
• 5 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1
• 6 the size of the parallelepiped: 3 × 3 × 4, the radius of the inscribed sphere 1.5

It is most profitable to take only the first stone.

题意：

题解：

/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^    ^ ^
 O      O
******************************/
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<vector>
#include<string>
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define  A first
#define B second
const int mod=1000000007;
const int MOD1=1000000007;
const int MOD2=1000000009;
const double EPS=0.00000001;
typedef __int64 ll;
const ll MOD=1000000007;
const int INF=1000000010;
const ll MAX=1ll<<55;
const double eps=1e-14;
const double inf=~0u>>1;
const double pi=acos(-1.0);
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
int mp[100005][4];
map <  int , map<int ,int> > m;
map <  int , map<int ,int> > pos;
int maxn,co,an;
int an1,an2;
int n;
int main()
{
    scanf("%d",&n);
    maxn=0;
    m.clear();
    pos.clear();
    for(int i=1; i<=n; i++)
    {
        scanf("%d %d %d",&mp[i][0],&mp[i][1],&mp[i][2]);
        sort(mp[i],mp[i]+3);
        if(maxn<mp[i][0]){
            maxn=mp[i][0];
            co=1;
            an=i;
        }
        if(m[mp[i][1]][mp[i][2]]>0)
        {
            int exm=m[mp[i][1]][mp[i][2]]+mp[i][0];
            if(maxn<min(exm,mp[pos[mp[i][1]][mp[i][2]]][1]))
            {
                maxn=min(exm,mp[pos[mp[i][1]][mp[i][2]]][1]);
                co=2;
                an1=pos[mp[i][1]][mp[i][2]];
                an2=i;
            }
        }
        if(m[mp[i][1]][mp[i][2]]<mp[i][0])
        {
           m[mp[i][1]][mp[i][2]]=max(m[mp[i][1]][mp[i][2]],mp[i][0]);
           pos[mp[i][1]][mp[i][2]]=i;
        }

    }if(co==1)
            printf("1
%d
",an);
        else
            printf("2
%d %d
",an1,an2);
    return 0;
}