Description

今天是星期天，小楠楠来找你玩“石头、剪刀、布游戏”。你正在学习信息学， 所以想了一种需要编程来玩的“石头、剪刀、布游戏”。首先，用数字 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 次。

Input Format

第一行 3 个整数 N,M,K。分别表示你出拳方式的周期长度、楠楠出拳方式的周 期长度和总共玩的次数。 
第二行有 N 个整数，每个整数为 1、2、3 其中之一。 
第三行有 M 个整数，每个整数为 1、2、3 其中之一。

Output Format

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

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

29

Hint

8 个数据： N,M 的范围是[1..100],K 的范围是[1…100,000]。 
2 个数据: N,M 的范围是[1..100],K 的范围是[1…1,000,000,000]

Source

南海区赛 2015南海小学 前缀和