← 返回题目列表

Codeforces · 1500/B

B. 两个枝形吊灯

中文机器翻译题面 查看原题

Vasya 是一家大型建筑公司的首席执行官。和其他大老板一样,他有一间宽敞、布置丰富的办公室,里面有两盏水晶吊灯。为了保持积极性,Vasya 需要每天改变办公室的灯光颜色。这就是为什么他订购了两盏可以循环改变颜色的吊灯。例如:红色--棕色--黄色--红色--棕色--黄色等。

有许多吊灯的颜色设置或颜色顺序不同。负责灯光的人犯了一个严重的错误——他们买了两个不同的枝形吊灯。

由于枝形吊灯不同,有时它们会具有相同的颜色,但有时会有所不同。当然,它看起来很糟糕,只会惹恼瓦夏。结果,当枝形吊灯第 $$$k$$$ 次点亮不同颜色时,Vasya 会变得非常生气,并且很可能会解雇购买枝形吊灯的人。

你的任务是计算它发生的日期(从安装吊灯的那天开始算)。你可以认为Vasya每天都在工作,没有周末和休息日。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 500\,000$$$; $$$1 \le k \le 10^{12}$$$) — 第一个和第二个吊灯的颜色数量以及颜色应该相差多少次才能激怒 Vasya。

第二行包含 $$$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$$$ 不同,因此有时吊灯的颜色会不同。

输出

打印单个整数 — Vasya 生气的日期索引。

示例

输入 #1

4 2 4
4 2 3 1
2 1

输出 #1

5

输入 #2

3 8 41
1 3 2
1 6 4 3 5 7 2 8

输出 #2

47

输入 #3

1 2 31
1
1 2

输出 #3

62

注意

在第一个示例中,枝形吊灯在 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$5$$$ 天有不同的颜色。这就是为什么答案是$$$5$$$。