A. Fast Food Restaurant

Tired of boring office work, Denis decided to open a fast food restaurant.

On the first day he made a portions of dumplings, b portions of cranberry juice and c pancakes with condensed milk.

The peculiarity of Denis’s restaurant is the procedure of ordering food. For each visitor Denis himself chooses a set of dishes that this visitor will receive. When doing so, Denis is guided by the following rules:

  • every visitor should receive at least one dish (dumplings, cranberry juice, pancakes with condensed milk are all considered to be dishes);
  • each visitor should receive no more than one portion of dumplings, no more than one portion of cranberry juice and no more than one pancake with condensed milk;
  • all visitors should receive different sets of dishes.

What is the maximum number of visitors Denis can feed?

Input

The first line contains an integer t (1 ≤ t ≤ 500) — the number of test cases to solve.

Each of the remaining t lines contains integers a, b and c (0 ≤ a,b,c ≤ 10) — the number of portions of dumplings, the number of portions of cranberry juice and the number of condensed milk pancakes Denis made.

Output

For each test case print a single integer — the maximum number of visitors Denis can feed.

Example

input

7
1 2 1
0 0 0
9 1 7
2 2 3
2 3 2
3 2 2
4 4 4

output

3
0
4
5
5
5
7

Note

In the first test case of the example, Denis can feed the first visitor with dumplings, give the second a portion of cranberry juice, and give the third visitor a portion of cranberry juice and a pancake with a condensed milk.

In the second test case of the example, the restaurant Denis is not very promising: he can serve no customers.

In the third test case of the example, Denise can serve four visitors. The first guest will receive a full lunch of dumplings, a portion of cranberry juice and a pancake with condensed milk. The second visitor will get only dumplings. The third guest will receive a pancake with condensed milk, and the fourth guest will receive a pancake and a portion of dumplings. Please note that Denis hasn’t used all of the prepared products, but is unable to serve more visitors.

Problem solving:

题意就是有三种不同的食物,给出三种食物的数量,问有多少种食物搭配的方案(可以用1种、2种或3种食物进行搭配,只要没出现过就可以)。

很明显先从只选1种食物开始,如果当前数量大于1,方案数就加一。

然后从2种食物开始搭配,优先贪心选择剩余数量最多的两种,然后再乱搞(两两选择)。

最后如果3种食物数量都大于1,就可以再加一种方案(选择三种食物)。

#include<bits/stdc++.h>
using namespace std;
const ll N = 1e5+7;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        int ans=0;
        if(a>0) a--,ans++;
        if(b>0) b--,ans++;
        if(c>0) c--,ans++;

        int k[3];
        k[0]=a;
        k[1]=b;
        k[2]=c;
        sort(k,k+3);

        if(k[2]>0 && k[1]>0) k[2]--,k[1]--,ans++;//先选择最多的两个
        //下面是乱搞的
        if(k[0]>0 && k[2]>0) k[0]--,k[2]--,ans++;
        if(k[1]>0 && k[0]>0) k[1]--,k[0]--,ans++;

        if(k[1]>0 && k[0]>0 && k[2]>0) ans++;
        cout<<ans<<endl;
     } 

    return 0;
}

B. Different Rules

Nikolay has only recently started in competitive programming, but already qualified to the finals of one prestigious Olympiad. There going to be n participants, one of whom is Nikolay. Like any good Olympiad, it consists of two rounds. Tired of the traditional rules, in which the participant who solved the largest number of problems wins, the organizers came up with different rules.

Suppose in the first round participant A took x-th place and in the second round — y-th place. Then the total score of the participant A is sum x + y. The overall place of the participant A is the number of participants (including A) having their total score less than or equal to the total score of A. Note, that some participants may end up having a common overall place. It is also important to note, that in both the first and the second round there were no two participants tying at a common place. In other words, for every i from 1 to n exactly one participant took i-th place in first round and exactly one participant took i-th place in second round.

Right after the end of the Olympiad, Nikolay was informed that he got x-th place in first round and y-th place in the second round. Nikolay doesn’t know the results of other participants, yet he wonders what is the minimum and maximum place he can take, if we consider the most favorable and unfavorable outcome for him. Please help Nikolay to find the answer to this question.

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases to solve.

Each of the following t lines contains integers n, x, y (1 ≤ n ≤ 109, 1 ≤ x, y ≤ n) — the number of participants in the Olympiad, the place that Nikolay took in the first round and the place that Nikolay took in the second round.

Output

Print two integers — the minimum and maximum possible overall place Nikolay could take.

Examples

input

1
5 1 3

output

1 3

input

1
6 3 4

output

2 6

Problem solving:

题意是说一共有n个人,有两轮比赛,你第一轮得了第a名。第二轮得了第b名。最后的总名次是按照这两次比赛和名次和来判断的,两轮的名次和越少总名次越高,问已知n,a,b的情况下,最好、最坏能得多少名。

注意两轮比赛中没有两人名次相同的情况,总名次会有相同的情况,例如5个人名次和分别是 4,4,4,8,10,那么这五个人的总名次就是3, 3, 3, 4, 5。

最坏情况就是总名次在你前面的人两轮的名次和都和你相同,这样最多会有a+b-1人(包括自己),而最多只有n人所以最坏情况就是min(n,a+b-1);

至于最好情况,感觉(乱搞)出来的

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,x,y;
        cin>>n>>x>>y;
        ll sum = x+y;
        //最好
        if(sum<n) cout<<1<<" ";
        else cout<<min(n,sum-n+1)<<" ";
        //最坏
        cout<<min(n,sum-1)<<endl; 
    }    
    return 0;
}

C1. Skyscrapers (easy version)

This is an easier version of the problem. In this version n ≤ 1000

The outskirts of the capital are being actively built up in Berland. The company “Kernel Panic” manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought n plots along the highway and is preparing to build n skyscrapers, one skyscraper per plot.

Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.

Formally, let’s number the plots from 1 to n. Then if the skyscraper on the i-th plot has ai floors, it must hold that ai is at most mi (1 ≤ ai ≤ mi). Also there mustn’t be integers j and k such that j < i < k and aj > ai < ak . Plots j and k are not required to be adjacent to i.

The company wants the total number of floors in the built skyscrapers to be as large as possible. Help it to choose the number of floors for each skyscraper in an optimal way, i.e. in such a way that all requirements are fulfilled, and among all such construction plans choose any plan with the maximum possible total number of floors.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of plots.

The second line contains the integers m1,m2,…,mn (1 ≤ mi ≤ 109) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.

Output

Print n integers ai — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.

If there are multiple answers possible, print any of them.

Examples

input

5
1 2 3 2 1

output

1 2 3 2 1

input

3
10 6 8

output

10 6 6

Note

In the first example, you can build all skyscrapers with the highest possible height.

In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer [10,6,6] is optimal. Note that the answer of [6,6,8] also satisfies all restrictions, but is not optimal.

Problem solving:

题意是说给你一个序列,让你修改成 j < i < k 情况下没有 aj > ai < ak 的序列,要求修改后的序列和最大。修改时每个数不能超过原来的大小。

这道题因为是easy版本的 ,数据范围比较小,一般情况下就可以用暴力。

我们只需要暴力检查每个点,把当前点当做最大的,依次往两边扫就可以了。

#include<bits/stdc++.h>
#define fi        first
#define se        second
#define PI        acos(-1)
#define LC(a)     ((a<<1))
#define RC(a)     ((a<<1)+1)
#define MID(a,b)  ((a+b)>>1)
#define mem(a, b) memset(a, b, sizeof(a))
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<ll,ll>   PLL;
typedef pair<ll,int>  PLI;
const int INF = 0X3F3F3F3F;
const int MIN = -(1<<30);
const ll N = 1e5+7;
int main()
{
    IOS();
    int n;
    cin>>n;
    ll a[1005];
    ll b[1005];
    ll c[1005];
    ll mxi=0;
    for(int i=0; i<n; i++) cin>>a[i];
    ll ans=0;
    ll num;
    for(int mxi=0;mxi<n;mxi++)
    {
        num = a[mxi];
        b[mxi] = a[mxi];
        for(int i=mxi-1; i>=0; i--)
        {
            if(a[i]>b[i+1]) b[i]=b[i+1];
            else b[i] = a[i];
            num+=b[i];
        }
        for(int i=mxi+1; i<n; i++)
        {
            if(a[i]>b[i-1]) b[i]=b[i-1];
            else b[i] = a[i];
            num+=b[i];
        }
        if(ans<num)
        {
            ans=num;
            for(int i=0; i<n; i++) c[i]=b[i];
        }
    }
    for(int i=0; i<n; i++)
        cout<<c[i]<<" ";
    cout<<endl;
    return 0;
}

C2. Skyscrapers (hard version)

这道题和C1是一模一样的,只是n从1000增加到了500 000。

待补!


一个好奇的人