Vasya is a CEO of a big construction company. And as any other big boss he has a spacious, richly furnished office with two crystal chandeliers. To stay motivated Vasya needs the color of light at his office to change every day. That's why he ordered both chandeliers that can change its color cyclically. For example: red – brown – yellow – red – brown – yellow and so on.

There are many chandeliers that differs in color set or order of colors. And the person responsible for the light made a critical mistake — they bought two different chandeliers.

Since chandeliers are different, some days they will have the same color, but some days — different. Of course, it looks poor and only annoys Vasya. As a result, at the $k$-th time when chandeliers will light with different colors, Vasya will become very angry and, most probably, will fire the person who bought chandeliers.

Your task is to calculate the day, when it happens (counting from the day chandeliers were installed). You can think that Vasya works every day without weekends and days off.


-----Input-----

The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 500000$; $1 \le k \le 10^{12}$) — the number of colors in the first and the second chandeliers and how many times colors should differ to anger Vasya.

The second line contains $n$ different integers $a_i$ ($1 \le a_i \le 2 \cdot \max(n, m)$) that describe the first chandelier's sequence of colors.

The third line contains $m$ different integers $b_j$ ($1 \le b_i \le 2 \cdot \max(n, m)$) that describe the second chandelier's sequence of colors.

At the $i$-th day, the first chandelier has a color $a_x$, where $x = ((i - 1) \mod n) + 1)$ and the second one has a color $b_y$, where $y = ((i - 1) \mod m) + 1)$.

It's guaranteed that sequence $a$ differs from sequence $b$, so there are will be days when colors of chandeliers differs.


-----Output-----

Print the single integer — the index of day when Vasya will become angry.


-----Examples-----

Input
4 2 4
4 2 3 1
2 1
Output
5
Input
3 8 41
1 3 2
1 6 4 3 5 7 2 8
Output
47
Input
1 2 31
1
1 2
Output
62


-----Note-----

In the first example, the chandeliers will have different colors at days $1$, $2$, $3$ and $5$. That's why the answer is $5$.

Difficulty: HARD
Tags: Number theory

Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
import sys, os
if os.environ['USERNAME'] == 'kissz':
	inp = open('in5.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass

def extgcd(a, b):
	if b == 0:
		x = 1
		y = 0
		return (a, x, y)
	(d, x, y) = extgcd(b, a % b)
	(x, y) = (y, x - y * (a // b))
	return (d, x, y)
(n, m, k) = map(int, inp().split())
A = [*map(int, inp().split())]
B = [*map(int, inp().split())]
(d, x, y) = extgcd(n, m)
l = n * m // d
ax = [-1] * 1000001
good_days = [l]
cnt = l
for i in range(n):
	ax[A[i]] = i
for i in range(m):
	if ax[B[i]] >= 0 and ax[B[i]] % d == i % d:
		c = i - ax[B[i]]
		y0 = (n * x * c // d + ax[B[i]]) % l
		good_days.append(y0)
		cnt -= 1
good_days.sort()
days = (k - 1) // cnt * l
rem = (k - 1) % cnt + 1
for (i, day) in enumerate(good_days):
	if day - i >= rem:
		days += rem + i
		break
print(days)


import math

def solve(n, m, k, a, b):
	d = math.gcd(n, m)
	x = 0
	y = 0
	for i in range(1, m):
		if (i * n - d) % m == 0:
			x = i
			y = (i * n - d) // m
			if y == 0:
				x += 1
				y += 1
			break
	common = {}
	common_count = 0
	colors = {}
	for i in range(len(a)):
		colors[a[i]] = i
	for i in range(len(b)):
		if b[i] in colors and (colors[b[i]] - i) % d == 0:
			common[colors[b[i]]] = i
			common_count += 1
	com = []
	for (key, val) in common.items():
		z = (val - key) // d
		com.append(int(z * x % (m // d) * n + key))
	new_k = k % (m * n // d - common_count)
	s = k // (m * n // d - common_count) * m * n // d
	if new_k == 0:
		new_k = m * n // d - common_count
		s -= m * n // d
	com = sorted(com)
	cur = -1
	for c in com:
		if new_k < c - cur:
			s += new_k
			return s
		new_k -= c - cur - 1
		s += c - cur
		cur = c
	return s + new_k
(n, m, k) = list(map(int, input().split()))
c1 = list(map(int, input().split()))
c2 = list(map(int, input().split()))
if n < m:
	print(solve(m, n, k, c2, c1))
else:
	print(solve(n, m, k, c1, c2))


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
from bisect import *
from math import gcd
import typing

def inv_gcd(a, b):
	a %= b
	if a == 0:
		return (b, 0)
	(s, t) = (b, a)
	(m0, m1) = (0, 1)
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		(s, t) = (t, s)
		(m0, m1) = (m1, m0)
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
	assert len(r) == len(m)
	n = len(r)
	(r0, m0) = (0, 1)
	for i in range(n):
		assert 1 <= m[i]
		r1 = r[i] % m[i]
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)
(N, M, k) = MI()
aa = LI()
bb = LI()
atoi = {a: i for (i, a) in enumerate(aa)}
g = gcd(N, M)
lcm = N * M // g
ss = []
for (j, b) in enumerate(bb):
	if b not in atoi:
		continue
	i = atoi[b]
	(r, t) = crt([atoi[b], j], [N, M])
	if t == 0:
		continue
	ss.append(r)
tot = lcm - len(ss)
ss.sort()
(p, k) = divmod(k, tot)
if k == 0:
	p -= 1
	k += tot
ans = p * lcm

def ok(m):
	i = bisect_left(ss, m)
	return m - i >= k
(l, r) = (0, lcm + 5)
while l + 1 < r:
	m = (l + r) // 2
	if ok(m):
		r = m
	else:
		l = m
print(ans + r)


import sys
input = sys.stdin.readline
from math import gcd
import bisect
(n, m, k) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

def Ext_Euc(a, b, axy=(1, 0), bxy=(0, 1)):
	(q, r) = divmod(a, b)
	if r == 0:
		return (bxy, b)
	rxy = (axy[0] - bxy[0] * q, axy[1] - bxy[1] * q)
	return Ext_Euc(b, r, bxy, rxy)

def Chirem(a, ma, b, mb):
	((p, q), d) = Ext_Euc(ma, mb)
	if (a - b) % d != 0:
		return -1
	return ((b * ma * p + a * mb * q) // d % (ma * mb // d), ma * mb // d)
GCD = gcd(n, m)
LCM = n * m // GCD
MAX = 2 * max(n, m) + 1
DAYA = [-1] * MAX
DAYB = [-1] * MAX
for i in range(n):
	DAYA[A[i]] = i
for i in range(m):
	DAYB[B[i]] = i
SAME = []
for i in range(MAX):
	if DAYA[i] == -1 or DAYB[i] == -1:
		continue
	x = Chirem(DAYA[i], n, DAYB[i], m)
	if x == -1:
		continue
	else:
		SAME.append(x[0])
xx = LCM - len(SAME)
ANS = k // xx * LCM
k %= xx
SAME.sort()
if k == 0:
	now = LCM - 1
	i = len(SAME) - 1
	while i >= 0 and now == SAME[i]:
		ANS -= 1
		i -= 1
		now -= 1
	print(ANS)
	exit()
OK = LCM - 1
NG = -1
while OK - NG > 1:
	mid = (OK + NG) // 2
	x = bisect.bisect(SAME, mid)
	if k <= mid + 1 - x:
		OK = mid
	else:
		NG = mid
print(OK + ANS + 1)


import sys
readline = sys.stdin.readline

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)
(N, M, K) = map(int, readline().split())
L = lcm(N, M)
gnm = gcd(N, M)
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
(g, p1, p2) = egcd(N, M)

def crt(b1, M1, b2, M2):
	s = (b2 - b1) // g
	return (b1 + s * M1 * p1) % L
Bi = dict()
for i in range(M):
	Bi[B[i]] = i
rr = []
for i in range(N):
	if A[i] in Bi:
		j = Bi[A[i]]
		if i % gnm == j % gnm:
			rr.append(crt(i, N, j, M))
rr.sort()
Z = len(rr)
ok = (L + 1) * (K + 1)
ng = 0
while abs(ok - ng) > 1:
	med = (ok + ng) // 2
	res = med - (med - 1) // L * Z
	xx = (med - 1) % L
	okk = 0
	ngg = Z + 1
	while abs(okk - ngg) > 1:
		medd = (okk + ngg) // 2
		if rr[medd - 1] <= xx:
			okk = medd
		else:
			ngg = medd
	res -= okk
	if res < K:
		ng = med
	else:
		ok = med
print(ok)


def main():
	(n, m, k) = map(int, input().split())
	aa = map(int, input().split())
	bb = map(int, input().split())
	if n < m:
		(n, m, aa, bb) = (m, n, bb, aa)
	x = y2 = 1
	y = x2 = 0
	(g, a) = (n, m)
	while a:
		q = g // a
		(g, a, x, y, x2, y2) = (a, g % a, x2, y2, x - x2 * q, y - y2 * q)
	(nm, nm2, mg) = (n // g * m, n * 2 + 1, m // g)
	(colors, common) = ([-1] * nm2, [-1] * nm2)
	for (i, a) in enumerate(aa):
		colors[a] = i
	for (i, b) in enumerate(bb):
		b = colors[b]
		if b != -1 in colors and (not (b - i) % g):
			common[b] = i
	common = [(a - i) // g * x % mg * n + i for (i, a) in enumerate(common) if a != -1]
	common_count = len(common)
	(res, k) = divmod(k, nm - common_count)
	if not k:
		k = nm - common_count
		res -= 1
	res *= nm
	common.sort()
	a = -1
	for b in common:
		b -= a
		if k < b:
			break
		k -= b - 1
		res += b
		a += b
	print(res + k)
main()


def main():
	(n, m, k) = list(map(lambda x: int(x), str(input()).split(' ')))
	a = list(map(lambda x: int(x), str(input()).split(' ')))
	b = list(map(lambda x: int(x), str(input()).split(' ')))
	if n < m:
		print(solve(m, n, k, b, a))
		return
	print(solve(n, m, k, a, b))

def solve(n, m, k, a, b):
	d = gcd(n, m)
	(x, y) = (0, 0)
	for i in range(1, m):
		if (i * n - d) % m == 0:
			x = i
			y = (i * n - d) // m
			if y == 0:
				x += 1
				y += 1
			break
	common = {}
	common_count = 0
	colors = {}
	for i in range(len(a)):
		colors[a[i]] = i
	for i in range(len(b)):
		if b[i] in colors and (colors[b[i]] - i) % d == 0:
			common[colors[b[i]]] = i
			common_count += 1
	com = []
	for (key, val) in common.items():
		z = (val - key) // d
		com.append(int(z * x % (m // d) * n + key))
	new_k = k % (m * n // d - common_count)
	s = k // (m * n // d - common_count) * m * n // d
	if new_k == 0:
		new_k = m * n // d - common_count
		s -= m * n // d
	com = sorted(com)
	cur = -1
	for c in com:
		if new_k < c - cur:
			s += new_k
			return s
		new_k -= c - cur - 1
		s += c - cur
		cur = c
	return s + new_k

def gcd(n, m):
	if n == m:
		return n
	if n < m:
		return gcd(m, n)
	if n % m == 0:
		return m
	return gcd(m, n % m)
main()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from math import gcd
	input = sys.stdin.readline

	def extgcd(a, b):
		if a == b:
			return (1, 0)
		if a == b == 0:
			return (0, 0)
		if b == 0:
			return (1, 0)
		AB = [a, b]
		while b:
			(a, b) = (b, a % b)
			AB.append(b)
		if len(AB) == 3:
			return (0, 1)
		k = AB[-2]
		x = 1
		y = -(AB[-4] // AB[-3])
		for i in range(len(AB) - 4, 0, -1):
			(a, b) = (AB[i - 1], AB[i])
			(x, y) = (y, x - y * (a // b))
		if k < 0:
			(x, y) = (-x, -y)
		return (x, y)
	(N, M, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	a2i = [-1] * 1000001
	b2i = [-1] * 1000001
	for (i, a) in enumerate(A):
		a2i[a] = i
	for (i, b) in enumerate(B):
		b2i[b] = i
	g = gcd(N, M)
	first_same = [-1] * N
	L = N * M // g
	for (i, a) in enumerate(A):
		j = b2i[a]
		if j == -1:
			continue
		if i % g != j % g:
			continue
		(x, y) = extgcd(N, -M)
		x *= (j - i) // g
		first_same[i] = N * x + i
		first_same[i] %= L
	FS = set()
	for i in range(N):
		if first_same[i] != -1:
			FS.add(first_same[i])
	cycle_num = L - len(FS)
	ans = K // cycle_num * L
	K %= cycle_num
	if K == 0:
		for v in range(L - 1, -1, -1):
			if v in FS:
				ans -= 1
			else:
				break
		print(ans)
		exit()
	ok = L - 1
	ng = -1
	mid = (ok + ng) // 2
	FS = list(FS)
	while ok - ng > 1:
		cnt = mid + 1
		for f in FS:
			if f <= mid:
				cnt -= 1
		if cnt >= K:
			ok = mid
		else:
			ng = mid
		mid = (ok + ng) // 2
	ans += ok + 1
	print(ans)
main()