The well-known Fibonacci sequence $F_0, F_1, F_2,\ldots $ is defined as follows:   $F_0 = 0, F_1 = 1$.  For each $i \geq 2$: $F_i = F_{i - 1} + F_{i - 2}$. 

Given an increasing arithmetic sequence of positive integers with $n$ elements: $(a, a + d, a + 2\cdot d,\ldots, a + (n - 1)\cdot d)$.

You need to find another increasing arithmetic sequence of positive integers with $n$ elements $(b, b + e, b + 2\cdot e,\ldots, b + (n - 1)\cdot e)$ such that:  $0 < b, e < 2^{64}$,  for all $0\leq i < n$, the decimal representation of $a + i \cdot d$ appears as substring in the last $18$ digits of the decimal representation of $F_{b + i \cdot e}$ (if this number has less than $18$ digits, then we consider all its digits). 


-----Input-----

The first line contains three positive integers $n$, $a$, $d$ ($1 \leq n, a, d, a + (n - 1) \cdot d < 10^6$).


-----Output-----

If no such arithmetic sequence exists, print $-1$.

Otherwise, print two integers $b$ and $e$, separated by space in a single line ($0 < b, e < 2^{64}$).

If there are many answers, you can output any of them.


-----Examples-----
Input
3 1 1

Output
2 1
Input
5 1 2

Output
19 5



-----Note-----

In the first test case, we can choose $(b, e) = (2, 1)$, because $F_2 = 1, F_3 = 2, F_4 = 3$.

In the second test case, we can choose $(b, e) = (19, 5)$ because:  $F_{19} = 4181$ contains $1$;  $F_{24} = 46368$ contains $3$;  $F_{29} = 514229$ contains $5$;  $F_{34} = 5702887$ contains $7$;  $F_{39} = 63245986$ contains $9$.

Difficulty: VERY_HARD
Tags: Number theory

Constructive algorithms

Starter code:

Solutions:
c = 9224175735 * 10 ** 8
m = 15 * 10 ** 17
(n, a, d) = map(int, input().split())
print(c * a % m + 1, c * d % m)


(n, a, d) = map(int, input().split())
print(368131125 * a % 10 ** 9 * 12 * 10 ** 9 + 1, 368131125 * d % 10 ** 9 * 12 * 10 ** 9)


def mult(a, b):
	c = [[0, 0], [0, 0]]
	global moder
	for k in range(0, 2):
		for i in range(0, 2):
			for j in range(0, 2):
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % moder
	return c

def powermod(a, exp):
	ret = [[1, 0], [0, 1]]
	while exp > 0:
		if exp % 2 == 1:
			ret = mult(ret, a)
		a = mult(a, a)
		exp >>= 1
	return ret

def eucinv(a, mod):
	(b, s, t) = (mod, 1, 0)
	while b:
		(a, b, q) = (b, a % b, a // b)
		(s, t) = (t, s - t * q)
	return s + mod if s < 0 else s
(n, a, d) = map(int, input().split())
moder = 10 ** 18
period = 12 * 10 ** 9
fn_1 = powermod([[0, 1], [1, 1]], period + 1)[0][1]
t = (fn_1 - 1) // 8 // 10 ** 9
invt = eucinv(t % 10 ** 6, 10 ** 6)
e = 125 * (d * invt % 10 ** 6)
e *= period
b = 125 * (a * invt % 10 ** 6)
b *= period
b += 1
print(b, e)


(_, a, d) = map(int, input().split())
ten_k = 10 ** 9
n = 12 * ten_k
t_inv = 1114945049
u = 125 * a * t_inv % ten_k
v = 125 * d * t_inv % ten_k
b = u * n + 1
e = v * n
print(b, e)


val = 3337867500
(N, A, D) = input().split()
N = int(N)
A = int(A)
D = int(D)
ans1 = val * A
ans2 = val * D
print(ans1, ans2)


(n, a, d) = map(int, input().split())
mod = 10 ** 12
step = pow(677449, 4 * 10 ** 11 - 1, mod)
print(step * a % mod * 1500000 + 1, step * d % mod * 1500000)


m = 15 * 10 ** 17
v = 708786750000
(n, a, d) = map(int, input().split())
print(v * a % m, v * d % m)


(o, m, k) = map(int, input().split())
print(368131125 * m % 10 ** 9 * 12 * 10 ** 9 + 1, 368131125 * k % 10 ** 9 * 12 * 10 ** 9)


val = 3337867500
(f, i, b) = map(int, input().split())
print(val * i, val * b)


(n, a, d) = map(int, input().split())
it = 614945049
N = 3 * 10 ** 9 // 2
u = a * it % 10 ** 9
v = d * it % 10 ** 9
print(u * N + 1, v * N)


(v, m) = (3337867500, 75 * 10 ** 8)
(n, a, d) = map(int, input().split())
print(v * a % m, v * d % m)


def exgcd(a, b):
	if b == 0:
		return (1, 0)
	(x, y) = exgcd(b, a % b)
	return (y, x - y * (a // b))

def inv(a, p):
	(x, y) = exgcd(a, p)
	return (x % p + p) % p

def xmul(a, b):
	c = [[0, 0], [0, 0]]
	for i in range(0, 2):
		for j in range(0, 2):
			for k in range(0, 2):
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % 10 ** 12
	return c

def xpow(a, b):
	s = [[1, 0], [0, 1]]
	while b:
		if b % 2:
			s = xmul(s, a)
		a = xmul(a, a)
		b //= 2
	return s

def fib(n):
	if n <= 1:
		return n
	return xmul([[1, 0], [0, 0]], xpow([[1, 1], [1, 0]], n - 1))[0][0]
t = fib(3 * 10 ** 6 + 1) // 10 ** 6
u = 15 * inv(t // 2, 10 ** 6)
(n, a, d) = map(int, input().split())
b = a * u * 10 ** 6 + 1
e = d * u * 10 ** 6
print(b, e)


(n, x, y) = map(int, input().split())
print(368131125 * x % 10 ** 9 * 12 * 10 ** 9 + 1, 368131125 * y % 10 ** 9 * 12 * 10 ** 9)


(n, a, d) = map(int, input().split())
A = 614945049
N = 10 ** 9
M = 3 * N // 2
print(A * a % N * M + 1, A * d % N * M)


(n, a, d) = map(int, input().split())
print(614945049 * a % 10 ** 9 * 15 * 10 ** 8 + 1, 614945049 * d % 10 ** 9 * 15 * 10 ** 8)


fib = 9224175735 * 10 ** 8
no = 15 * 10 ** 17
(z, x, y) = map(int, input().split())
print(fib * x % no + 1, fib * y % no)


value = 3337867500
(a, b, c) = map(int, input().split())
print(value * b, value * c)


x = 370878675000
(n, a, b) = map(int, input().split())
print(a * x, b * x)


(s, a, b) = map(int, input().split())
print(368131125 * a % 10 ** 9 * 12 * 10 ** 9 + 1, 368131125 * b % 10 ** 9 * 12 * 10 ** 9)


val = 3337867500
(K, B, Z) = map(int, input().split())
print(val * B, val * Z)


(a, t, h) = map(int, input().split())
print(368131125 * t % 10 ** 9 * 12 * 10 ** 9 + 1, 368131125 * h % 10 ** 9 * 12 * 10 ** 9)


cons = 3337867500
Inputs = list((int(x) for x in input().split()))
n = Inputs[0]
a = Inputs[1]
d = Inputs[2]
print(cons * a, cons * d)


val = 3337867500
(N, A, D) = map(int, input().split())
print(val * A, val * D)


re = input().split()
n = int(re[0])
a = int(re[1])
d = int(re[2])
m = 10 ** 9
n = 15 * 10 ** 8
print(a * 614945049 % m * n + 1, d * 614945049 % m * n)


(s, i, d) = map(int, input().split())
print(368131125 * i % 10 ** 9 * 12 * 10 ** 9 + 1, 368131125 * d % 10 ** 9 * 12 * 10 ** 9)


v = 3337867500
(f, i, b) = map(int, input().split())
print(v * i, v * b)


v = 3337867500
(n, a, d) = map(int, input().split())
print(v * a, v * d)


(v, m) = (3337867500, 15 * 10 ** 9)
(n, a, d) = map(int, input().split())
print(v * a % m, v * d % m)


val = 3337867500
(n, a, d) = map(int, input().split())
print(val * a, val * d)


(n, a, d) = [int(s) for s in input().split()]
print(a * 445049 * 15 * 10 ** 5 + 1, d * 445049 * 15 * 10 ** 5)


v = 708786750000
(n, a, d) = map(int, input().split())
print(v * a, v * d)


val = 3337867500
(n, a, b) = map(int, input().split())
print(val * a, val * b)


(n, a, d) = map(int, input().split())
it = 114945049
N = 12 * 10 ** 9
u = 125 * a * it % 10 ** 9
v = 125 * d * it % 10 ** 9
print(u * N + 1, v * N)


(n, a, d) = map(int, input().split())
(b, e) = (a * 5 * 945049 * 3000000 + 1, d * 5 * 945049 * 3000000)
print(b, e)


(n, a, d) = map(int, input().split())
pis = 12 * 1000000000
bas = 368131125
print(bas * a % 1000000000 * pis + 1, bas * d % 1000000000 * pis)


(n, a, d) = map(int, input().split())
print((614945049 * 1500000000 * a + 1) % 1500000000000000000, 614945049 * 1500000000 * d % 1500000000000000000)


value = 3337867500
(n, a, d) = map(int, input().split())
print(value * a, value * d)