CF1500B Two chandeliers

Vasya 是一家大型建筑公司的 CEO。和其他大老板一样，他有一个宽敞、豪华的办公室，里面有两盏水晶吊灯。为了保持动力，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_j \le 2 \cdot \max(n, m)$），表示第二盏吊灯的颜色序列。 第 $i$ 天，第一盏吊灯的颜色为 $a_x$，其中 $x = ((i - 1) \bmod n) + 1$；第二盏吊灯的颜色为 $b_y$，其中 $y = ((i - 1) \bmod m) + 1$。 保证序列 $a$ 与序列 $b$ 不同，因此一定存在颜色不同的天数。

输出一个整数，表示 Vasya 会生气的那一天的编号。

在第一个样例中，吊灯颜色不同的天分别是第 $1$、$2$、$3$ 和 $5$ 天。因此答案是 $5$。 由 ChatGPT 4.1 翻译