Codeforces Round #432 (Div. 2) ABC

Arpa is researching the Mexican wave.

There are n spectators in the stadium, labeled from 1 to n. They start the Mexican wave at time 0.

At time 1, the first spectator stands.
At time 2, the second spectator stands.
...
At time k, the k-th spectator stands.
At time k + 1, the (k + 1)-th spectator stands and the first spectator sits.
At time k + 2, the (k + 2)-th spectator stands and the second spectator sits.
...
At time n, the n-th spectator stands and the (n - k)-th spectator sits.
At time n + 1, the (n + 1 - k)-th spectator sits.
...
At time n + k, the n-th spectator sits.

Arpa wants to know how many spectators are standing at time t.

Input

The first line contains three integers n, k, t (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ n, 1 ≤ t < n + k).

Output

Print single integer: how many spectators are standing at time t.

Examples

Input

10 5 3

Output

Input

10 5 7

Output

Input

10 5 12

Output

3

三个判断

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 110;
 5 int main(){
 6     int n, k, t;
 7     cin >> n >> k >> t;
 8     if(t <= k) {
 9         printf("%d
",t);
10     } else if(t <= n) {
11         printf("%d
",k);
12     } else {
13         printf("%d
",k+n-t);
14     }
15     return 0;
16 }

Arpa is taking a geometry exam. Here is the last problem of the exam.

You are given three points a, b, c.

Find a point and an angle such that if we rotate the page around the point by the angle, the new position of a is the same as the old position of b, and the new position of b is the same as the old position of c.

Arpa is doubting if the problem has a solution or not (i.e. if there exists a point and an angle satisfying the condition). Help Arpa determine if the question has a solution or not.

Input

The only line contains six integers a_x, a_y, b_x, b_y, c_x, c_y (|a_x|, |a_y|, |b_x|, |b_y|, |c_x|, |c_y| ≤ 10⁹). It's guaranteed that the points are distinct.

Output

Print "Yes" if the problem has a solution, "No" otherwise.

You can print each letter in any case (upper or lower).

Examples

Input

0 1 1 1 1 0

Output

Yes

Input

1 1 0 0 1000 1000

Output

No


如果abc三点共线或者|ab| != |bc| 就时No  否则就时Yes
可惜三点共线没写好，总测没过去。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 110;
 5 struct Point{
 6     ll x, y;
 7 }a[4];
 8 ll dist(Point aa, Point b) {
 9     return (aa.x-b.x)*(aa.x-b.x)+(aa.y-b.y)*(aa.y-b.y);
10 }
11 bool cmp(Point x, Point y) {
12     return x.x < y.x;
13 }
14 bool check(){
15     sort(a+1,a+4,cmp);
16     if((a[2].y-a[1].y)*(a[3].x-a[2].x) == (a[3].y-a[2].y)*(a[2].x-a[1].x)) return true;
17 
18     return false;
19 }
20 int main(){
21     cin >> a[1].x >> a[1].y >> a[2].x >> a[2].y >> a[3].x >> a[3].y;
22     if(dist(a[1],a[2]) != dist(a[2],a[3])){
23         return 0*printf("No
");
24     } else if(check()){
25         return 0*printf("No
");
26     }else {
27         printf("Yes
");
28     }
29     return 0;
30 }

You are given set of n points in 5-dimensional space. The points are labeled from 1 to n. No two points coincide.

We will call point a bad if there are different points b and c, not equal to a, from the given set such that angle between vectors $\text{[math]}$ and $\text{[math]}$ is acute (i.e. strictly less than $\text{[math]}$ ). Otherwise, the point is called good.

The angle between vectors $\text{[math]}$ and $\text{[math]}$ in 5-dimensional space is defined as $\text{[math]}$ , where $\text{[math]}$ is the scalar product and $\text{[math]}$ is length of $\text{[math]}$ .

Given the list of points, print the indices of the good points in ascending order.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 10³) — the number of points.

The next n lines of input contain five integers a_i, b_i, c_i, d_i, e_i (|a_i|, |b_i|, |c_i|, |d_i|, |e_i| ≤ 10³) — the coordinates of the i-th point. All points are distinct.

Output

First, print a single integer k — the number of good points.

Then, print k integers, each on their own line — the indices of the good points in ascending order.

Examples

Input

Output

1
1

Input

Output

0

可以直接暴力过。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1010;
 5 struct Point{
 6     ll a, b, c, d, e;
 7 }nod[N];
 8 bool vis[N];
 9 ll check(Point aa, Point bb, Point cc) {
10     return (bb.a-aa.a)*(cc.a-aa.a)+(bb.b-aa.b)*(cc.b-aa.b)+(bb.c-aa.c)*(cc.c-aa.c)+(bb.d-aa.d)*(cc.d-aa.d)+(bb.e-aa.e)*(cc.e-aa.e);
11 }
12 int main(){
13     int n;
14     memset(vis, true, sizeof(vis));
15     cin >> n;
16     for(int i = 1; i <= n; i ++) {
17         cin >> nod[i].a >> nod[i].b >> nod[i].c >> nod[i].d >> nod[i].e;
18     }
19     int k = n;
20     for(int i = 1; i <= n; i ++) {
21         for(int j = 1; j <= n; j ++) {
22             for(int l = j+1; l <= n; l ++) {
23                 if(i != j && i != l) {
24                     if(check(nod[i], nod[j], nod[l]) > 0) {
25                         vis[i] = false;
26                         k--;
27                         goto tt;
28                     }
29                 }
30             }
31         }
32         tt:;
33     }
34     printf("%d
",k);
35     int cnt = 0;
36     for(ll i = 1; i <= n; i ++) {
37         if(vis[i]) {
38             cnt ++;
39             printf("%lld ",i);
40         }
41     }
42     if(k!=0)printf("
");
43     return 0;
44 }

Codeforces Round #432 (Div. 2) ABC

A. Arpa and a research in Mexican wave

B. Arpa and an exam about geometry

C. Five Dimensional Points