Problem G. Geometric similarity ≡

Statement

There are two simple (without self-intersections) polygons, each represented by a sequence of vertices in either clockwise or counter-clockwise order.

Your program must determine whether the polygons are similar, that is, whether one of them can be transformed into another by applying zero or more of the following operations:

• scaling all edges by a non-zero constant;
• rotating by 90^∘ in any direction around some fixed point;
• translation (offset by a vector);
• orientation changing (from clockwise to counter-clockwise and vice-versa).

Input format

Input contains integer n, followed by 2 ⋅ n vertices (first one polygon, then another), represented by pairs of integers: (x_i, y_i).

Output format

Output must contain a single integer: 1, if polygons are similar, 0 otherwise.

Constraints

It is guaranteed that both polygons are non-degenerate, i.e. have an area strictly greater than zero.

All edges also have non-zero length.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 3 ≤ n ≤ 10⁵

Sample tests

5
-300 300
-100 500
 200 400
 200 200
-100 100

 250 120
 150 220
  50 120
 100 -30
 200 -30

1

5
 100 200
   0 400
 300 300
 300 100
   0   0

 350 150
 150 320
  50 220
 100   0
 200   0

0