题目描述

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

例如：N=4，你的前 4 次出拳方式是“石头、剪刀、布、布”，用数字表示即：”1 2 3 3”。M=5，楠楠前 5 次出拳方式是“剪刀、石头、石头、布、布” ，用 数字表示即：”2 1 1 3 3”。K=10 时，情况如下表：

你共赢了 5 次。

输入格式

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

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

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

输出格式

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

样例

输入

5 6 100

输出

1 3 2 2 1
3 3 1 1 1 2
29

提示

8 个数据： NM 的范围是[1..100]K 的范围是[1…100000]。

2 个数据: NM 的范围是[1..100]K 的范围是[1…1000000000]

来源

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