Codeforces Round 707 (Div. 1, по задачам Открытой олимпиады школьников по программированию) |
---|
Закончено |
Вася — директор крупной строительной компании. Как и у всякого большого начальника у него есть большой, солидно обставленный кабинет, в котором висят две хрустальные люстры. Так сложилось, что Васе проще думать, если свет в комнате каждый день разного цвета. Когда Вася отдавал распоряжение о том, как именно оформлять его кабинет, он также указал, что ему нужны две таких люстры, чтобы в них каждый день цвет освещения изменялся по какому-нибудь циклу. Например, по такому: красный – коричневый – желтый – красный – коричневый – желтый, и так по кругу.
В продаже было несколько люстр, отличающихся друг от друга набором цветов в цикле или порядком. По какой-то ошибке, а может из-за невнимательности, человек, ответственный за выбор люстр, купил две разные люстры.
Из-за того, что люстры разные, в некоторые дни они будут светить одинаково, а в некоторые — по-разному. Естественно, это не солидно, и вообще раздражает Васю, так что когда в $$$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$$$.
Название |
---|