题目描述

瓦西娅是一家大型建筑公司的老板。作为一位大老板，他拥有一个宽敞且装饰庄重的办公室，里面悬挂着两盏水晶吊灯。瓦西娅发现，如果每天房间里的灯光颜色不同，他会更容易思考。因此，在布置办公室时，他特别要求两盏吊灯的灯光颜色每天按照某种循环模式变化。例如，循环可以是：红色-棕色-黄色-红色-棕色-黄色，依此类推循环。

市场上有多款吊灯，区别在于颜色循环的集合或顺序不同。由于某种失误或疏忽，负责选购吊灯的员工买了两盏不同的吊灯。

因为两盏吊灯不同，有些日子它们的灯光颜色会一致，而有些日子则会不同。显然，这种情况显得不够庄重，而且令瓦西娅感到恼火。因此，当第 $k$ 次出现今天吊灯灯光颜色不同的事件时，瓦西娅会非常生气并解雇某人（很可能是购买吊灯的员工）。你的任务是计算，从安装吊灯的第一天开始，经过多少天会发生这种情况。假设瓦西娅非常热爱工作，每天都会到办公室，没有节假日和周末。

输入格式

第一行包含三个整数 $n, m, k$ $(1 \leq n, m \leq 500000, 1 \leq k \leq 10^{12})$，分别表示第一盏吊灯的颜色数量、第二盏吊灯的颜色数量，以及吊灯颜色不同需要发生多少次才会使瓦西娅非常生气。

第二行包含 $n$ 个互不相同的整数 $a_i$ $(1 \leq a_i \leq 2 \cdot \max(n, m))$，定义第一盏吊灯的颜色序列。

第三行包含 $m$ 个互不相同的整数 $b_j$ $(1 \leq b_j \leq 2 \cdot \max(n, m))$，定义第二盏吊灯的颜色序列。

在第 $i$ 天，第一盏吊灯显示颜色 $a_x$，其中 $x = ((i - 1) \bmod n) + 1$；第二盏吊灯显示颜色 $b_y$，其中 $y = ((i - 1) \bmod 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

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。