# 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:

#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:

#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:

#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;
}