题目描述

今天是星期天，小楠楠来找你玩"石头、剪刀、布游戏"。你正在学习信息学，所以想了一种需要编程来玩的"石头、剪刀、布游戏"。首先，用数字 $1, 2, 3$ 分别表示出石头、剪刀、布。其次，你确定自己前 $N$ 次"石头、剪刀、布"的出拳方法，下面 $N$ 次再次同样出拳，…，周而复始；也要求楠楠确定他前 $M$ 次的出拳方法，然后周而复始。问第 $K$ 次后，你赢了几次？

例如：$N=4$，你的前 $4$ 次出拳方式是"石头、剪刀、布、布"，用数字表示即：$1, 2, 3, 3$。$M=5$，楠楠前 $5$ 次出拳方式是"剪刀、石头、石头、布、布"，用数字表示即：$2, 1, 1, 3, 3$。$K=10$ 时，你共赢了 $5$ 次。

输入格式

第一行 $3$ 个整数 $N, M, K$。分别表示你出拳方式的周期长度、楠楠出拳方式的周期长度和总共玩的次数。

第二行有 $N$ 个整数，每个整数为 $1$、$2$、$3$ 其中之一。

第三行有 $M$ 个整数，每个整数为 $1$、$2$、$3$ 其中之一。

输出格式

一个整数，表示 $K$ 轮出拳后，你赢的次数。

样例

5 6 100
1 3 2 2 1
3 3 1 1 1 2

29

数据范围

• 对于 $80\%$ 的数据：$N, M$ 的范围是 $[1, 100]$，$K$ 的范围是 $[1, 100000]$
• 对于 $100\%$ 的数据：$N, M$ 的范围是 $[1, 100]$，$K$ 的范围是 $[1, 1000000000]$