After buying gifts, Beo suddenly realized that he had received too many small denomination notes. Beo wants to exchange the amount of money he has for as few notes as possible. In the store, there are denominations of ~20~ dong, ~10~ dong, ~5~ dong and ~1~ dong. Please help Beo exchange ~b~ dong in the store. Because it is a large store, the number of banknotes is temporarily unlimited.

Input

• A single line contains the number ~b~ ~(0 ≤ b ≤ 10^6)~.

Output

• Consists of several lines, each with the following format:
  • ~X~ and ~Y~ - where ~X~ is the denomination and ~Y~ is the number of bannotes of the denomination ~X~.

Example Input

72

Example Output

20 3
10 1
1 2

Note

• Output in order of decreasing denomination. If the number of banknotes of any denomination is zero, don't output that denomination.