Easter Sundays P35547

Easter Sunday is a mobile holiday corresponding to the first Sunday after the first full moon of the spring. Write a program to compute the day D and the month M of the Easter Sunday of every given year Y.

Below, := indicates assignment, div indicates integer division, and mod indicates the remainder of the integer division. To solve this problem, use the Gauss method:

• Compute
  1. k := Y ‍div ‍100
  2. x := Y  ‍mod ‍ 19
  3. b := Y  ‍mod ‍ 4
  4. c := Y  ‍mod ‍ 7
  5. q := k ‍div ‍4
  6. p := (13+8k) ‍div ‍25
  7. y := (15−p+k−q)  ‍mod ‍ 30
  8. z := (19x+y)  ‍mod ‍ 30
  9. n := (4+k−q)  ‍mod ‍ 7
  10. e := (2b+4c+6z+n)  ‍mod ‍7
• If z+e ≤ 9, then D := 22+z+e and M := 3.
• Otherwise, if z=29 and e=6, then D := 19 and M := 4.
• Otherwise, if z=28 and e=6 and x>10, then D := 18 and M := 4.
• Otherwise, D := z+e−9 and M := 4.

Input

Input consists of several natural numbers between 1800 and 9999.

Output

Print the day and the month of the Easter Sunday of each year.