Can you find it

Time Limit: 8000/5000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Given a prime number $C(1 \leq C \leq 2\times 10^5)$, and three integers k1, b1, k2 $(1 \leq k1, k2, b1 \leq 10^9)$. Please find all pairs (a, b) which satisfied the equation $a^{k1 \cdot n + b1}$ + $b^{k2 \cdot n - k2 + 1}$ = 0 (mod C)(n = 1, 2, 3, ...).

Input

There are multiple test cases (no more than 30). For each test, a single line contains four integers C, k1, b1, k2.

Output

First, please output "Case #k: ", k is the number of test case. See sample output for more detail.
Please output all pairs (a, b) in lexicographical order. $(1 \leq a, b < C)$. If there is not a pair (a, b), please output -1.

Sample Input

23 1 1 2

Sample Output

Case #1: 1 22

Hint

hujie

Source

2015 ACM/ICPC Asia Regional Shanghai Online

提交代码