crystal fixtures are unique, every so often they will have a similar shading, yet occasionally — unique. Obviously, it looks poor and just pesters Vasya. Subsequently, at the kk-th time when ceiling fixtures will light with various tones, Vasya will get extremely upset and, most presumably, will fire the individual who purchased light fixtures. Your errand is to compute the day, when it occurs (counting from the day ceiling fixtures were introduced
Correct answer Will be upvoted else downvoted.
Since crystal fixtures are unique, every so often they will have a similar shading, yet occasionally — unique. Obviously, it looks poor and just pesters Vasya. Subsequently, at the kk-th time when ceiling fixtures will light with various tones, Vasya will get extremely upset and, most presumably, will fire the individual who purchased light fixtures.
Your errand is to compute the day, when it occurs (counting from the day ceiling fixtures were introduced). You can feel that Vasya works each day without ends of the week and days off.
Input
The main line contains three integers nn, mm and kk (1≤n,m≤5000001≤n,m≤500000; 1≤k≤10121≤k≤1012) — the quantity of tones in the first and the subsequent light fixtures and how frequently tones ought to contrast to outrage Vasya.
The subsequent line contains nn various integers aiai (1≤
The third line contains mm various integers bjbj (1≤bi≤2⋅max(n,m)1≤bi≤2⋅max(n,m)) that portray the subsequent light fixture's grouping of tones.
At the ii-th day, the main light fixture has a shading axax, where x=((i−1)modn)+1)x=((i−1)modn)+1) and the subsequent one has a shading byby, where y=((i−1)modm)+1)y=((i−1)modm)+1).
It's reliable that grouping aa contrasts from arrangement bb, so there are will be days when shades of light fixtures varies.
Output
Print the single integer — the record of day when Vasya will get upset
Step by step
Solved in 3 steps with 1 images
