The following languages are only available languages for the problems from the contest

VK Cup 2015 - Wild Card Round 1:

- Picat 0.9

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Diophantine equation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an equation *A* * *X* + *B* * *Y* = *C*, *A*, *B*, *C* are positive integer coefficients, *X* and *Y* are variables which can have positive integer values only. Output the number of solutions of this equation and the solutions themselves.

Input

The only line of input contains integers *A*, *B* and *C* (1 ≤ *A*, *B*, *C* ≤ 1000), separated with spaces.

Output

In the first line of the output print the number of the solutions *N*. In the next *N* lines print the solutions, formatted as "*XY*", sorted in ascending order of *X*, one solution per line.

Examples

Input

3 5 35

Output

2

5 4

10 1

Input

3 35 5

Output

0

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2018 04:00:51 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|