【比赛报告】AHSOFNU codeforces训练赛1 by hzwer NOIP练习赛卷三

比赛链接

A.The Game Of Parity

Description

There are n cities in Westeros. The i-th city is inhabited by ai people. Daenerys and Stannis play the following game: in one single move, a player chooses a certain town and burns it to the ground. Thus all its residents, sadly, die. Stannis starts the game. The game ends when Westeros has exactly k cities left.

The prophecy says that if the total number of surviving residents is even, then Daenerys wins: Stannis gets beheaded, and Daenerys rises on the Iron Throne. If the total number of surviving residents is odd, Stannis wins and everything goes in the completely opposite way.

Lord Petyr Baelish wants to know which candidates to the throne he should support, and therefore he wonders, which one of them has a winning strategy. Answer to this question of Lord Baelish and maybe you will become the next Lord of Harrenholl.

Input

The first line contains two positive space-separated integers, n and k (1 ≤ k ≤ n ≤ 2·105) — the initial number of cities in Westeros and the number of cities at which the game ends.

The second line contains n space-separated positive integers ai (1 ≤ ai ≤ 106), which represent the population of each city in Westeros.

Output

Print string “Daenerys” (without the quotes), if Daenerys wins and “Stannis” (without the quotes), if Stannis wins.

Examples

Input

3 1
1 2 1

Output

Stannis

Input

3 1
2 2 1

Output

Daenerys

Input

6 3
5 20 12 7 14 101

Output

Stannis

Note

In the first sample Stannis will use his move to burn a city with two people and Daenerys will be forced to burn a city with one resident. The only survivor city will have one resident left, that is, the total sum is odd, and thus Stannis wins.

In the second sample, if Stannis burns a city with two people, Daenerys burns the city with one resident, or vice versa. In any case, the last remaining city will be inhabited by two people, that is, the total sum is even, and hence Daenerys wins.

---

博弈论。分几类讨论：
1.如果一方可以把奇数拿光，那么Daenerys赢了；
2.如果一方可以把偶数拿光，如果k是奇数则Stannis赢了，否则Daenerys赢了；
3.双方都不能拿空奇或偶，那么最后行动的人就可以选择奇或偶，一定赢。

#include<cstdio>
int n,k,a,odd,even;
int main()
{//freopen("in.txt","r",stdin);scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a);if(a&1)odd++;else even++;}if(n==k){if(odd&1)puts("Stannis");else puts("Daenerys");return 0;}int step=n-k;if(step/2>=odd)return puts("Daenerys"),0;//最后只剩偶数 if(step/2>=even)//最后只剩奇数 {if(k&1)puts("Stannis");else puts("Daenerys");return 0;}//奇偶都有，谁最后走谁赢 if(step&1)return puts("Stannis"),0;return puts("Daenerys"),0;
}

总结

分类讨论

---

B.Happy Line

题目链接

Description

Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person a stands just behind person b, then person a can pay person b 1 dollar, then a and b get swapped. Of course, if person a has zero dollars, he can not swap places with person b.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.

Input

The first line contains integer n (1 ≤ n ≤ 200 000) — the number of residents who stand in the line.

The second line contains n space-separated integers ai (0 ≤ ai ≤ 109), where ai is the number of Berland dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line.

Output

If it is impossible to make all the residents happy, print “?” without the quotes. Otherwise, print in the single line n space-separated integers, the i-th of them must be equal to the number of money of the person on position i in the new line. If there are multiple answers, print any of them.

Examples

Input

2
11 8

Output

9 10

Input

5
10 9 7 10 6

Output

?

Input

3
12 3 3

Output

4 4 10

Note

In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line.

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

---

可以发现交换前后对于每个人权值加下标的和恒定。可以把权值加下标构成新权值，判断是否能构成一个严格递增序列。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,a[N];
int main()
{//freopen("in.txt","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]+=i;sort(a+1,a+n+1);for(int i=1;i<n;i++)if(a[i]==a[i+1]||a[i]-i<0||a[n]-n<0)return puts(":("),0;for(int i=1;i<=n;i++)printf("%d%c",a[i]-i,i==n?'\n':' ');return 0;
}

总结

找规律

---

C.Glass Carving

题目链接

Description

Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular w mm  ×  h mm sheet of glass, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how.

In order not to waste time, he decided to practice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Leonid does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments.

After each cut Leonid tries to determine what area the largest of the currently available glass fragments has. Since there appear more and more fragments, this question takes him more and more time and distracts him from the fascinating process.

Leonid offers to divide the labor — he will cut glass, and you will calculate the area of the maximum fragment after each cut. Do you agree?

Input

The first line contains three integers w, h, n (2 ≤ w, h ≤ 200 000, 1 ≤ n ≤ 200 000).

Next n lines contain the descriptions of the cuts. Each description has the form H y or V x. In the first case Leonid makes the horizontal cut at the distance y millimeters (1 ≤ y ≤ h - 1) from the lower edge of the original sheet of glass. In the second case Leonid makes a vertical cut at distance x (1 ≤ x ≤ w - 1) millimeters from the left edge of the original sheet of glass. It is guaranteed that Leonid won’t make two identical cuts.

Output

After each cut print on a single line the area of the maximum available glass fragment in mm2.

Examples

Input

4 3 4
H 2
V 2
V 3
V 1

Output

8
4
4
2

Input

7 6 5
H 4
V 3
V 5
H 2
V 1

Output

28
16
12
6
4

Note

Picture for the first sample test:

Picture for the second sample test:

---

显然对于每个长和宽都会有矩形对应，我们需要知道每次操作后最长的长和宽。分别对长和宽用两个set维护切点和切出的长度。

#include<cstdio>
#include<iostream>
#include<set>
using namespace std;
set<int>r,c;
multiset<int>a,b;
int w,h,n;
int main()
{//freopen("in.txt","r",stdin);std::ios::sync_with_stdio(false);cin>>w>>h>>n;r.insert(0);r.insert(h);c.insert(0);c.insert(w);a.insert(w);b.insert(h);set<int>::iterator it;while(n--){char ch;int pos;cin>>ch>>pos;if(ch=='H'){it=r.lower_bound(pos);int right=*it,left=*(--it);b.erase(b.lower_bound(right-left));b.insert(pos-left);b.insert(right-pos);r.insert(pos);}else{it=c.lower_bound(pos);int right=*it,left=*(--it);a.erase(a.lower_bound(right-left));a.insert(pos-left);a.insert(right-pos);c.insert(pos);}printf("%lld\n",1ll*(*--a.end())*(*--b.end()));}return 0;
}

总结

我lrl就是累死，死机房外边把键盘扔下去，也不用超时的STL。真香

---

D.Clique Problem

Description

The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph G. It is required to find a subset of vertices C of the maximum size such that any two of them are connected by an edge in graph G. Sounds simple, doesn’t it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph.

Consider n distinct points on a line. Let the i-th point have the coordinate xi and weight wi. Let’s form graph G, whose vertices are these points and edges connect exactly the pairs of points (i, j), such that the distance between them is not less than the sum of their weights, or more formally: |xi - xj| ≥ wi + wj.

Find the size of the maximum clique in such graph.

Input

The first line contains the integer n (1 ≤ n ≤ 200 000) — the number of points.

Each of the next n lines contains two numbers xi, wi (0 ≤ xi ≤ 109, 1 ≤ wi ≤ 109) — the coordinate and the weight of a point. All xi are different.

Output

Print a single number — the number of vertexes in the maximum clique of the given graph.

Examples

Input

4
2 3
3 1
6 1
0 2

Output

3

Note

If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars!

The picture for the sample test.

---

由题意满足 $|x_i-x_j|\ge w_i+w_j$的点对 $(i,j)$ 可以连边。对公式化简得 $x_i-w_i\ge x_j+w_j$ 或 $x_i+w_i\le x_j-w_j$。所以把所有点按照 $x_i+w_i$ 升序排序，和前面的点比较。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n;
ll x,w;
pair<ll,ll>p[N];
int main()
{//freopen("in.txt","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&x,&w),p[i]=make_pair(x+w,x-w);sort(p+1,p+n+1);ll pre=-0x7fffffff,cnt=0;for(int i=1;i<=n;i++)if(p[i].second>=pre)cnt++,pre=p[i].first;printf("%lld\n",cnt);return 0;
}

总结

主考对公式的化简。

---

赛后总结

顺了一波hzwer大佬挑的题来做，美滋滋。感觉可以先把他挑出来的codeforces的题做了再说。
涉及知识点：博弈论、STL的使用姿势、对公式化简后排序。