B. Две люстры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася — директор крупной строительной компании. Как и у всякого большого начальника у него есть большой, солидно обставленный кабинет, в котором висят две хрустальные люстры. Так сложилось, что Васе проще думать, если свет в комнате каждый день разного цвета. Когда Вася отдавал распоряжение о том, как именно оформлять его кабинет, он также указал, что ему нужны две таких люстры, чтобы в них каждый день цвет освещения изменялся по какому-нибудь циклу. Например, по такому: красный – коричневый – желтый – красный – коричневый – желтый, и так по кругу.

В продаже было несколько люстр, отличающихся друг от друга набором цветов в цикле или порядком. По какой-то ошибке, а может из-за невнимательности, человек, ответственный за выбор люстр, купил две разные люстры.

Из-за того, что люстры разные, в некоторые дни они будут светить одинаково, а в некоторые — по-разному. Естественно, это не солидно, и вообще раздражает Васю, так что когда в $$$k$$$-й раз наступит событие «сегодня люстры светят разными цветами», Вася очень разозлится и кого-то уволит (вероятно, сотрудника, купившего люстры). Ваша задача – понять, на какой день, начиная со дня установки люстр, это случится. Считайте, что Вася очень любит работать, поэтому работает каждый день, без праздников и выходных.

Входные данные

В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 500\,000$$$; $$$1 \le k \le 10^{12}$$$) — количество цветов в первой люстре, количество цветов во второй люстре и сколько раз люстры должны гореть разным цветом, чтобы Вася очень разозлился.

Во второй строке даны $$$n$$$ различных чисел $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot \max(n, m)$$$), задающих последовательность цветов для первой люстры.

В третьей строке даны $$$m$$$ различных чисел $$$b_j$$$ ($$$1 \le b_i \le 2 \cdot \max(n, m)$$$), задающих последовательность цветов для второй люстры.

В $$$i$$$-й день первая люстра светит цветом $$$a_x$$$, где $$$x = ((i - 1) \mod n) + 1)$$$, а вторая цветом $$$b_y$$$, где $$$y = ((i - 1) \mod m) + 1)$$$.

Гарантируется, что последовательность $$$a$$$ не совпадает тождественно с последовательностью $$$b$$$, а значит лампы будут периодически раздражать Васю.

Выходные данные

Выведите одно число — через сколько дней Вася очень разозлится.

Примеры
Входные данные
4 2 4
4 2 3 1
2 1
Выходные данные
5
Входные данные
3 8 41
1 3 2
1 6 4 3 5 7 2 8
Выходные данные
47
Входные данные
1 2 31
1
1 2
Выходные данные
62
Примечание

В первом тесте из условия люстры будут гореть разными цветами в дни $$$1$$$, $$$2$$$, $$$3$$$ и $$$5$$$. Соответственно ответом является $$$5$$$.