# 4-point polyline

You are given a rectangular grid of lattice points from (0, 0) to (n, m) inclusive. You have to choose exactly 4 different points to build a polyline possibly with self-intersections and self-touching. This polyline should be as long as possible.

A polyline defined by points p 1, p 2, p 3, p 4 consists of the line segments p 1p 2, p 2p 3, p 3p 4, and its length is the sum of the lengths of the individual line segments.

Input

The only line of the input contains two integers n and m (0 ≤ n, m ≤ 1000). It is guaranteed that grid contains at least 4 different points.

Output

Print 4 lines with two integers per line separated by space — coordinates of points p 1, p 2, p 3, p 4 in order which represent the longest possible polyline.

Judge program compares your answer and jury’s answer with 10 - 6 precision.

Examples

input

1 1

output

1 10 01 00 1

input

0 10

output

0 10 100 00 9

Solution:

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const double MAGIC = 3.14159265358979; inline double dist(int a, int b, int c, int d) {   return sqrt(1.0 * ((a - c) * (a - c) + (b - d) * (b - d))); } double d; int main() {   int n, m;   scanf("%d %d", &n, &m);   vector < pair > a;   for (int x = 0; x <= n; x++) {     for (int y = 0; y <= m; y++) {       if (dist(0, 0, x, y) < MAGIC || dist(0, m, x, y) < MAGIC ||           dist(n, 0, x, y) < MAGIC || dist(n, m, x, y) < MAGIC) {         a.push_back(make_pair(x, y));       }     }   }   int k = a.size();   for (int i = 0; i < k; i++) {     for (int j = 0; j < k; j++) {       d[i][j] = dist(a[i].first, a[i].second, a[j].first, a[j].second);     }   }   double ans = -1.0;   int a1 = -1;   int a2 = -1;   int a3 = -1;   int a4 = -1;   for (int i = 0; i < k; i++) {     for (int j = 0; j < k; j++) {       if (i != j) {         for (int p = 0; p < k; p++) {           if (i != p && j != p) {             for (int q = 0; q < k; q++) {               if (i != q && j != q && p != q) {                 double sum = d[i][j] + d[j][p] + d[p][q];                 if (sum > ans) {                   ans = sum;                   a1 = i;                   a2 = j;                   a3 = p;                   a4 = q;                 }               }             }           }         }       }     }   }   printf("%d %d\n", a[a1].first, a[a1].second);   printf("%d %d\n", a[a2].first, a[a2].second);   printf("%d %d\n", a[a3].first, a[a3].second);   printf("%d %d\n", a[a4].first, a[a4].second);   return 0; }