We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Geometry
  4. Xrange's Pancakes

Xrange's Pancakes

Xrange makes the best polygonal pancakes in PancakeLand. To grow the business, they hired line cooks to be pancake rotators and flippers.

A regular n-gon has vertices, flipping axes, and rotation points. We define the following:

  • Flipping Axes
    • If is odd, each flipping axis passes through a single vertex and the midpoint of the opposite side (resulting in total flipping axes).
    • If is even, flipping axes pass through every pair of opposing vertices and flipping axes pass through every pair of opposing sides.
    • The angle between consecutive axes is degrees.
    • A -flipper flips the pancake at axis number .
  • Rotation Points
    • There are types of rotators.
    • A -rotator rotates the the pancake clockwise by degrees. The types of rotators are -rotator, -rotator, …, -rotator.

rsz_1hackerrankprob1.png

Each pancake passes through a long line of rotators and flippers who change the polygonal pancake's orientation during cooking. Xrange wants to hire one more rotator or flipper to restore the pancake to its initial orientation for plating.

Given and the sequence of rotators and flippers that the pancake passes through, determine which type of rotator or flipper must be added to the end of the line to restore the pancake to its initial orientation.

Input Format

The first line contains two space-separated integers denoting the respective values of (the number of vertices in the polygonal pancake) and (the number of line cooks performing the transformations).
Each line of the subsequent lines describes a line cook in the form of two space-separated integers, and (respectively). If , line cook is a rotator; if , line cook is a flipper. The second value, , is the integer by which they flip or rotate the pancake; flippers flip the pancake along axis number , and rotators rotate the pancake by degrees.

Constraints

Output Format

Print a single line with two space-separated integers denoting the respective values of and for the rotator or flipper needed at the end of the line in order to restore the pancake to its initial orientation.

Sample Input 0 

5 5
1 1
1 3
2 2
2 2
1 4

Sample Output 0 

1 2

Explanation 0

The diagram below demonstrates the sequence of flips and rotations performed on the polygonal pancake as it makes its way down the line:

Once the pancake reaches the end of the line, it needs to be rotated (which is ) by to be restored to its original orientation. Thus, we print 1 2 on a new line.

Sample Input 1 

6 5
1 2
1 4
2 3
2 2
2 4

Sample Output 1 

2 5