Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol.…
- User
Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is h1 and height of Abol is h2. Each second, Mike waters Abol and Xaniar.
So, if height of Xaniar is h1 and height of Abol is h2, after one second height of Xaniar will become and height of Abol will become where x1, y1, x2 and y2 are some integer numbers and denotes the remainder of a modulo b.
Mike is a competitive programmer fan. He wants to know the minimum time it takes until height of Xania is a1 and height of Abol is a2.
Mike has asked you for your help. Calculate the minimum time or say it will never happen. Input
The first line of input contains integer m (2 ≤ m ≤ 106).
The second line of input contains integers h1 and a1 (0 ≤ h1, a1 < m).
The third line of input contains integers x1 and y1 (0 ≤ x1, y1 < m).
The fourth line of input contains integers h2 and a2 (0 ≤ h2, a2 < m).
The fifth line of input contains integers x2 and y2 (0 ≤ x2, y2 < m).
It is guaranteed that h1 ≠ a1 and h2 ≠ a2.
Output
Print the minimum number of seconds until Xaniar reaches height a1 and Abol reaches height a2 or print -1 otherwise.
Examples
Input
5 4 2 1 1 0 1 2 3
Output
3
Input
1023 1 2 1 0 1 2 1 1
Output
-1
Note
In the first sample, heights sequences are following:
Xaniar:
Abol:
Assistant
We are given a problem: Mike has a frog Xaniar and a flower Abol. Each second, they are watered, and their heights change according to a recurrence: at time t, height of Xaniar is h1_t, height of Abol is h2_t. Given parameters: m, h1, a1, x1, y1 for Xaniar, and similarly h2, a2, x2, y2 for Abol. The update rule: h(t+1) = (x * h(t) + y) mod m. Starting at time 0 with heights h1_0 = h1 (given), h2_0 = h2. We want the smallest time t such that h1_t = a1 and h2_t = a2.
We need to compute minimum t >= 0 meeting both conditions, or -1 if impossible.
We need to handle m up to 1e6. So we can simulate up to some limit, but could be large (cycles). We need to analyze the structure of the linear congruential generator: h -> (x*h + y) mod m. This is an affine transformation modulo m. It may eventually become periodic after some preperiod, but since modulus m is not necessarily prime, and transformation may not be invertible if x and m not coprime. So the sequence is deterministic and eventually periodic, but we need to find times when h1_t = a1 and h2_t = a2.
We can consider each sequence individually: find all times t where h1_t = a1, and similarly for h2_t = a2. Then find common t.
But the number of such t could be infinite if the sequences cycle. The sequences eventually fall into a cycle. For each target value, we need to find the set of times when it occurs. This set may be of the form: some finite set of times in the preperiod, and then infinite arithmetic progression in the cycle (if target appears in cycle). Then we need to find intersection with other such set.
Because m <= 1e6, the total number of states is at most m, so the preperiod + cycle length <= m. So we can compute the sequence up to at most m steps and record times of occurrence of a1 and a2. Then we can characterize their occurrence patterns.
Approach: simulate both sequences for up to 2*m steps maybe to capture first occurrence and cycle detection. But careful: Since we need to find minimum t that works for both, and if both sequences eventually have periodic occurrences, we need to solve for t in linear congruences. But because the cycle may have a period that is not the same as the length of the cycle (i.e., the transformation may have a period for each state, but the whole cycle may have length L, after which the state repeats; if a1 appears at some positions in the cycle, then it appears at times t = t0 + k * L for k >= some minimum such that t >= first occurrence? Actually if we start from given h, the sequence eventually enters a cycle. Suppose we simulate and find:
-
For sequence 1: It may have a preperiod: times from 0 to some p1-1 are not in cycle, then from time p1 onward, it repeats with period L1. In other words, for t >= p1, h1_t = h1_{t+L1}. The cycle length L1 is the period of the cycle.
-
Similarly for sequence 2.
Now for target a1, we can record:
-
Possibly some occurrences in preperiod (times < p1). These are finite.
-
Possibly some occurrences in cycle: if a1 appears at some times in the cycle, then let the set of offsets within the cycle (relative to start of cycle) be positions S1 (set of integers in [0, L1-1] such that at time p1 + s, h1 = a1). Then for any t = p1 + s + k*L1 where k >= 0 integer, we have h1_t = a1. Similarly for a2.
Thus we need to find the smallest t (non-negative) such that:
either t is in the intersection of the finite sets (preperiod occurrences) and also satisfies other condition, or t is in the combination: one from preperiod of one and cycle of the other, etc. Actually we need to consider all possibilities.
Since m up to 1e6, we can simulate each sequence for at most m steps to detect cycle and record occurrences. Then we can attempt to compute minimal t.
But there might be case where one target appears only in preperiod, while the other appears only in cycle after preperiod, and they don't coincide. Or both appear only in preperiod, then we need to check if any t is common.
Since maximum m=1e6, we can simply simulate both sequences up to m steps to collect all times when each equals target, up to maybe some bound like 2*m? However the minimal t might be larger than m if one target appears only after a long preperiod? Actually preperiod length can be up to m (since at most m distinct states before repeating). So if both targets appear in the cycle, the minimal t may be less than m but could also be larger if the first common occurrence is later? But if both are in cycles, we can have t = first occurrence in cycle of sequence1 and we need to see if it matches sequence2's occurrences. The first common t could be larger than m if the cycles align later, but since cycles are periodic, we can solve a congruence to find the smallest t >= max(preperiod start) that satisfies both. That t might be > m, but we can compute it efficiently using number theory.
Thus we need to algorithmically compute:
- For each sequence i:
- Determine if a_i is ever reached.
- If reached, find the first time t_i_first (the minimal t where h_i(t)=a_i).
- Determine if a_i is in the cycle. That is, does it appear after the cycle start? Possibly it could appear only in preperiod and never again.
- For cycle: find the start time of cycle (i.e., first time entering the cycle) p_i, and the cycle length L_i. Also find all offsets s in the cycle where the state equals a_i. Since the cycle repeats, there could be multiple positions within the cycle where a_i occurs. In a deterministic function, each state has a unique successor, so the cycle is a simple cycle (or possibly with tails). Within the cycle, the values are distinct? Not necessarily; there could be repeated values? Actually since it's a function from a finite set to itself, cycles are simple cycles where each node has exactly one incoming edge (from previous node) but nodes can have multiple incoming edges from outside the cycle. However within the cycle, all nodes are distinct because if a node repeated, it would be a cycle of smaller length. So all states in the cycle are distinct. Therefore a_i can appear at most once in the cycle (if it is part of the cycle). Because if a_i is in the cycle, it appears exactly once per cycle (since cycle states are unique). But is it possible that a_i appears in the cycle multiple times? Only if the cycle contains that state multiple times, which would mean the state repeats, which would imply a shorter cycle. So no. So for any value that is in the cycle, it appears exactly at one offset within the cycle (if it's part of the cycle). However note: the function may not be invertible, but cycles are still simple loops. So each state in the cycle is visited exactly once per period. So the set S_i (offsets where a_i occurs) will be either empty (if a_i not in cycle) or a single offset s_i (0 <= s_i < L_i). But there is also possibility that a_i occurs in the preperiod multiple times? Possibly, but the preperiod can have repeated states? The preperiod consists of states before entering the cycle; they are all distinct until the cycle is entered. Since it's a deterministic function on a finite set, the trajectory is eventually periodic: there is a first time t0 where the state repeats a previous state, and from then on it cycles. All states before t0 are distinct. So any value can appear at most once in the preperiod, because if it appeared twice before the cycle, that would create a cycle earlier. Actually could a value appear twice in preperiod? Not if states are distinct. Since state is the height value, which is a number from 0 to m-1. If the same height appears twice, then the sequence will repeat from there, forming a cycle. So the first repeat defines the cycle start. Thus before the cycle start, all states are distinct. So each height appears at most once in the preperiod. So a_i can appear at most once in preperiod, and if it appears in cycle, exactly once per cycle.
Thus each target can have:
- Not reached at all.
- Reached exactly once (either in preperiod or in cycle). But if reached in cycle, it's reached infinitely many times, at times t = t0 + k*L (where t0 is the first time it is encountered, which could be either in preperiod if the first occurrence is before the cycle start, or if it first appears after cycle start, that's t0). But careful: if a_i appears in the preperiod and also later in the cycle? Is that possible? Since the preperiod values are distinct from cycle values? Actually the cycle may include the same value as a preperiod value? If a value appears in the preperiod, later when we enter the cycle, the cycle could contain the same value? But since the preperiod state that leads to the cycle, the cycle states are all distinct. Could a preperiod state be equal to some cycle state? That would mean when we hit that state again later, it's the start of the cycle. Indeed the first repeated state marks the beginning of the cycle. So if a value appears in the preperiod and then again in the cycle, that would mean that the first occurrence of that value is in preperiod, then later the same value appears, and that later appearance is when the cycle begins? But the definition: cycle start is the first time a state repeats. So if a value appears in the preperiod and then later again, that later occurrence is the first repeat, and it marks that the value is part of the cycle and also the start of the cycle. In that case, the value occurs twice overall: once in preperiod and then infinitely many times in the cycle (since after entering the cycle, it repeats every period). But is that possible? Let's consider a simple example: m=5, transformation h -> (h+1) mod 5, start at 0. Sequence: 0,1,2,3,4,0,1,... The first repeat is at t=5, state 0 repeats earlier state at t=0. So cycle start is at t=0? Actually the first time a state repeats is at t=5 with state 0 which appeared at t=0. So the cycle is from t=0 onward? Usually we define the eventual cycle: there exists μ (preperiod length) and λ (cycle length) such that for all t >= μ, h(t) = h(t+λ). In this example, μ=0, λ=5. But note that state 0 appears at t=0 and t=5. So it appears in preperiod? There is no preperiod. But consider a case with actual tail: Suppose transformation: from 0->1, 1->2, 2->2 (self-loop). Start at 0: 0,1,2,2,2,... Here first repeat: state 2 repeats at t=3 (t=2 and t=3). So μ=2? Actually for t>=2, the sequence is constant 2, so cycle length λ=1? Since h(t)=h(t+1) for t>=2. The cycle includes state 2. Now state 2 appears first at t=2 (which is the start of the cycle) and never in the preperiod. So preperiod has distinct states 0,1. Now could a state appear both in tail and in cycle? Suppose we have transformation: 0->1,1->2,2->3,3->2 (so tail: 0,1 then cycle: 2,3,2,3...). The first repeat: state 2 appears at t=2 and then again at t=4? Actually sequence: 0,1,2,3,2,3,... The first repeat is at t=4 (state 2) which previously at t=2. So μ=2 (preperiod length) because from t=2 onward, it's periodic? But after t=2, we have 2,3,2,3,... which is periodic with period 2. So the cycle includes states 2 and 3. The state 2 appears at t=2 (first in cycle) and also later. State 3 appears at t=3. Neither appears in preperiod (0 and 1 are distinct). So state 2 is not in preperiod; first occurrence is at cycle start. Now can a state appear in preperiod and also in cycle? For that to happen, a state that appears before the cycle start must reappear later as part of the cycle. That would be the first repeat, and that state would be the start of the cycle. For example, consider transformation: 0->1,1->2,2->0 (3-cycle). Start at 0: 0,1,2,0,1,... Here the first repeat is state 0 at t=3, which also appears at t=0. So the cycle is the whole sequence, and the preperiod length μ=0? Because the sequence is periodic from start? Actually we can set μ=0 because from t=0 it's periodic? But typical definition: the first time a state repeats is at t=3. The states before that (0,1,2) are all distinct. The cycle starts at the first occurrence of the repeated state, which is at t=0? But that's ambiguous. Usually we find the smallest μ and λ such that the sequence is eventually periodic: there exists μ such that for all t>=μ, h(t)=h(t+λ). In this example, with period 3, we can take μ=0, λ=3 because h(t)=h(t+3) for all t>=0 (since it's periodic from the start). But the first repeat occurs at t=3 with state 0, but we can still consider μ=0. So the tail can be zero. In this case, state 0 appears at t=0 and t=3, both in the cycle. So it's not in preperiod; the preperiod is empty. For a state to appear in preperiod and also in cycle, we would need a non-zero tail where a state appears in the tail and then later in the cycle (not as the first occurrence of the cycle start). That would require that the first repeat is not the state from tail that later repeats? Let's attempt to construct: Suppose we have states: 0,1,2,3,1,... Here we see 1 repeats at t=4, previously at t=1. The first repeat is at t=4. So the tail would be [0,1,2,3] before the cycle? But after t=1 we have 2, then 3, then 1, then? Let's define mapping: 0->1, 1->2, 2->3, 3->1. Start at 0: 0,1,2,3,1,2,3,1,... The first repeat is 1 at t=4 (previously at t=1). The cycle is from t=1 onward? Actually from t=1, the sequence is 1,2,3,1,2,3,... So it's periodic from t=1 with period 3. But note: t=1 is part of the cycle, but the state at t=0 (0) is not in the cycle. So μ=1, λ=3. In this case, state 1 appears at t=1 (first in cycle) and also later. It does not appear in the tail before t=1 except maybe at t=0? t=0 is 0, not 1. So 1 is not in tail. What about state 2? It appears at t=2 (in cycle) and later; not in tail. State 3 at t=3 (in cycle). So no overlap. In order for a state to appear in tail and then again in cycle, we need a tail that leads to a cycle, and some state in tail equals a state that is also in the cycle but not the entry point? That would create a repeat that is earlier: If a state in tail equals a state in cycle, then when we hit that state in cycle, it's the same as earlier state in tail, causing a repeat earlier than we might think. But the first repeat defines the start of the cycle as the first time a state repeats. If a state S appears in tail at time t0, and later at time t1 > t0 we encounter S again, then the first repeat is at time t1 with state S. The cycle start is the first occurrence of that state (t0) because after t0, the sequence will eventually repeat after t1-t0? Actually if we encounter a repeat at time t1 of a state seen at time t0, then for all t >= t0, the sequence is periodic with period (t1 - t0)? Not necessarily: Consider the possibility that after t0, the sequence goes on and eventually returns to S at t1. That indicates that from t0 onward, the sequence enters a cycle of length (t1-t0). However, there may be other states before t0 that are not part of the cycle. The tail length is t0 (the number of steps before entering the cycle). So the cycle includes the state at t0, t0+1, ..., t1-1. So S is at both ends of the cycle. So S is part of the cycle. So any state that repeats later must be in the cycle, and the first occurrence of that state is the start of the cycle. Therefore any state that appears in the tail (preperiod) cannot appear again in the cycle because if it did, that first appearance would be the start of the cycle, thus moving tail to earlier time. So tail states are distinct from cycle states. So each value appears either only in the tail (if it occurs before cycle start and never again) or only in the cycle (if it occurs at cycle start onward, possibly infinite times). It cannot appear both in tail and later in cycle. Because if it appears later in cycle, the first occurrence would be in tail, but then that state repeats later, which means that state is part of the cycle, but then tail would be before that first occurrence? Actually we need to formalize:
We have a deterministic function f: S->S, S finite. Starting from initial state s0, we produce sequence s0, s1=f(s0), s2=f(s1), ... The sequence is eventually periodic: there exist smallest μ >= 0 and λ >= 1 such that for all t >= μ, s_{t+λ}=s_t, and the states s_μ, s_{μ+1}, ..., s_{μ+λ-1} are all distinct. Then the tail (preperiod) consists of s_0,..., s_{μ-1}. The cycle consists of s_μ,..., s_{μ+λ-1}. Since all states in the cycle are distinct, and also distinct from tail states? Could a tail state equal a cycle state? Suppose there exists i<μ and j>=μ such that s_i = s_j. Then consider the smallest such j. Then since s_i = s_j, and the sequence is deterministic, we have s_{i+1}=f(s_i)=f(s_j)=s_{j+1}, and so on. This would imply that from i onward, the sequence repeats with period j-i. In particular, for t >= i, s_{t+(j-i)}=s_t. That would make μ <= i, because the sequence becomes periodic from i. But we defined μ as the smallest index such that periodic holds. So if i < μ, then μ would be <= i, contradiction. Therefore, no tail state equals any cycle state. So indeed tail and cycle are disjoint sets.
Thus each value appears at most once overall? Actually a value can appear at most once in tail and at most once in cycle (if it's in the cycle, it appears exactly once per cycle, but since tail and cycle are disjoint, it cannot appear in both). So for a target a, it can be either:
- Not in tail nor in cycle => never reached.
- In tail at exactly one time t0 (0 <= t0 < μ). Then it's reached only at that time.
- In cycle: then it appears exactly once per cycle at times t = μ + s, where s is the offset (0 <= s < λ). Additionally, it could also be that the first occurrence is at the start of the cycle (μ) or later within the cycle. But it is reached for all t = μ + s + k*λ for k >= 0.
Now we need to find the smallest t that is in both sets.
We can compute for each sequence:
-
First occurrence time first_i (the smallest t such that h_i(t)=a_i). Also check if it's in cycle or preperiod.
-
If a_i is in cycle, we also need the cycle start μ_i and cycle length λ_i, and the offset s_i (such that μ_i + s_i = first occurrence maybe, but careful: The first occurrence might be before μ_i? Actually if a_i is in cycle, its first occurrence is at μ_i + s_i where s_i is the offset within the cycle. But it's possible that the first occurrence is actually before μ_i? No, because tail and cycle are disjoint, so if a_i is in cycle, it does not appear in tail, so its first occurrence is at the time it appears first in the cycle, which is >= μ_i. So first_i >= μ_i. However, it could be that a_i appears exactly at μ_i (i.e., the start of the cycle). Then first_i = μ_i.
-
If a_i is not in cycle (i.e., only in tail), then we can still have μ_i, λ_i defined for the sequence (the eventual cycle) but a_i is not part of it. In that case, it occurs only at one time t = first_i, and we need to treat that.
Now the intersection problem reduces to:
Let T1 be the set of times t where h1(t)=a1. It can be:
- If only in tail: T1 = {t1} (single).
- If in cycle: T1 = {first1 + kλ1 : k >= 0} (but ensure that first1 >= μ1? Actually the times for which h1(t)=a1 are exactly t = first1 + kλ1 for all k >= 0, because after first1, every λ1 steps it repeats. However, does first1 equal μ1 + s? Yes. But also, there might be no other occurrences before first1 (since tail disjoint). So set is arithmetic progression starting at first1 with difference λ1.
But wait: what if the first occurrence is exactly at μ1? Then times are μ1 + k*λ1. That's correct.
But also what if there is a case where a_i appears in the tail and also later? Not possible as argued.
But what if a_i appears in the tail and also later because the tail leads to cycle that contains a_i? Not possible because tail and cycle are disjoint. So safe.
Thus we have two possible types for each sequence.
Now we need to find min t >= 0 such that t in T1 and t in T2.
Case analysis:
-
Both only in tail: then T1 = {t1}, T2 = {t2}. Answer is t1 if t1 = t2; else -1.
-
One only in tail, the other in cycle (or both in cycle? we treat separately). If one is only tail at time t_single, we need to check if the other sequence also attains target at that same time. For the one in cycle, we need to see if t_single satisfies the arithmetic progression: t_single >= first_cycle? And t_single ≡ first_cycle (mod λ). Actually condition: t_single must be >= first_cycle and (t_single - first_cycle) % λ == 0. Also need to ensure that t_single is not before the cycle start? But if t_single < first_cycle, then it's not in the cycle's times because the cycle's times start at first_cycle. However, could the cycle's target appear earlier if the first occurrence is later? Only if t_single = first_cycle? But t_single might be > first_cycle? So we check. If it matches, answer is t_single. Otherwise -1.
But also consider scenario where the tail one's time t_single might be after cycle start but not matching the arithmetic progression. Then no.
- Both in cycle: Then we have two arithmetic progressions: t = first1 + k1 * λ1, t = first2 + k2 * λ2, with k1,k2 >= 0 integers. Need the smallest t >= max(first1, first2) (since both must be at least their first occurrences) satisfying the congruence: t ≡ first1 (mod λ1) and t ≡ first2 (mod λ2). However, there is a nuance: Could t be less than first1 or first2? No, because those are the first times the respective targets appear. So we need t >= max(first1, first2). Also note that first1 and first2 are not necessarily the cycle start; they are the first occurrence times, which are at least μ_i. So we need to solve the system of linear congruences.
But careful: The arithmetic progression is infinite but starting at first_i. However, if the progression includes times before first_i? No, because k must be nonnegative; the smallest t from that progression is first_i. So we need t = first1 + k1λ1 = first2 + k2λ2 for some nonnegative integers k1,k2.
This is a classic problem: find the smallest t that satisfies t ≡ a (mod n) and t ≡ b (mod m) and t >= max(a,b). Since a and b are residues modulo n,m respectively, but they are not necessarily less than the moduli. However we can rewrite as t = a + nx, t = b + my, with x,y >= 0 integers. We need to find minimal t.
We can treat as solving: a + nx ≡ b (mod m) => nx ≡ b-a (mod m). Let d = gcd(n, m). Solution exists iff (b-a) % d == 0. If exists, we can find smallest nonnegative x0 modulo m/d, then t = a + nx0. That t may be less than max(a,b)? Possibly, because x0 could be 0 giving t = a, but if a < b, then t = a may not satisfy the second progression unless a ≡ b (mod m) and also a >= b? Actually if a < b, and we get t = a, but a is not >= b? But we need t = b + my, so if t = a < b, then we would need y negative? Because b + my = a => y = (a-b)/m which is negative fraction not integer unless a=b. So t must be at least max(a,b) because from the second progression, t = b + my with y>=0 gives t>=b; similarly from first gives t>=a. So we need t >= max(a,b). So after finding a solution t0 (maybe the smallest nonnegative solution in terms of congruence, which could be less than max(a,b)), we may need to add multiples of LCM(n,m) to reach at least the lower bound. However, there is also the condition that x,y must be nonnegative. For a given t, we can compute x = (t-a)/n, y = (t-b)/m. They must be integers and >=0.
So the standard method: find the smallest t that satisfies both congruences and t >= max(a,b). This can be done by solving the linear congruence equation and then adjusting.
But we also need to consider the possibility that the cycles might have different starting points (the first occurrence times) and the periods. However, note: The progression is not exactly all t ≡ a (mod n) for all integers, because the congruence class is defined modulo n, but the starting point a might be >= n? Actually the usual representation: t = a + nx, x>=0. This is equivalent to t ≡ a (mod n) and t >= a. Since a is the smallest such t in the progression. But note that if we consider t ≡ a mod n, the residues are taken modulo n, so we can reduce a modulo n: let r1 = a mod n. Then all t with t ≡ r1 (mod n) and t >= a are valid. But if we take t = r1 + nx, for x >= ceil((a - r1)/n). So we can set base = r1, and offset = first1 - r1, which is multiple of n. So essentially t = r1 + n*x, with x >= some minimal k1 (where k1 = (first1 - r1)/n). Similarly for second.
Thus we can compute the condition using standard CRT with lower bounds.
Simplify: Since first1 and first2 are the minimal times, we can compute:
Let L = lcm(λ1, λ2) if both cycles exist.
We need to find smallest t such that:
t >= first1, t >= first2, t ≡ first1 (mod λ1), t ≡ first2 (mod λ2).
If no solution, answer -1.
That's the typical CRT with moduli not necessarily coprime.
Implementation details:
We can simulate each sequence to detect:
- visited times for each state? Because m up to 1e6, we can allocate arrays time[m] initialized to -1. Then we simulate from start h (given) computing next = (x * cur + y) % m, tracking step count t from 0. For each cur, if time[cur] != -1, we have found a repeat. That indicates we have entered a cycle. But careful: We need to differentiate between first occurrence of a target and cycle detection. We'll simulate until we have either visited a state twice, or we have stepped enough to cover all m+1 states? Actually we can stop when we encounter a state that we've seen before. At that point, we have determined the preperiod (the first time we saw that state) and the cycle length.
Procedure for one sequence (i):
Initialize array firstSeen of size m with -1. cur = h_i (given), t = 0. while firstSeen[cur] == -1: firstSeen[cur] = t if cur == a_i: record occurrence: we can store first occurrence (if not yet recorded) as t. cur = (x_i * cur + y_i) % m t++
Now when we exit loop, we have at current time t, cur is a state that we have seen before at time firstSeen[cur] = t0. So the cycle start index is t0, and the cycle length is t - t0. Also, we have recorded all occurrences of a_i up to time t-1 (i.e., before the repeat). But we might have missed occurrences after entering the cycle? Actually we have simulated up to the point just before updating to the repeated state? Let's examine: The loop condition checks firstSeen[cur] before processing cur? Our simulation approach: At start t=0, cur = initial h. We check if firstSeen[cur] == -1, then record firstSeen, check target, then update. So after loop, we have just tried to process cur that is already seen. So we have not processed that cur (i.e., we haven't recorded its target or time for that state). So the last state (cur) is the one that caused the loop exit. Its time firstSeen[cur] = t0 is the first time we saw it. So we have visited states for times 0,1,...,t-1 (since after t steps, we are at cur, but we haven't processed time t? Let's be precise:
Pseudo:
t = 0 cur = h while firstSeen[cur] == -1: firstSeen[cur] = t if cur == a: record t as occurrence if first time? cur = (x*cur + y) % m t++
When loop exits, we have just identified that cur (the state we are about to process) has been seen before. So we have stored times for all states we visited before this moment, i.e., we have processed times 0..t-1 inclusive? Let's step: initially t=0, cur=h0. If not seen, we record firstSeen[h0]=0, check target, then update cur to h1, t becomes 1. Then loop condition checks cur = h1. So after each iteration, we increment t and update cur. So when loop exits, we have just done the update to a state that is already seen. At that moment, we have recorded times for the states at t = 0,1,...,t-1? Let's do an example: start t=0, cur=h0 (unseen). Record time0. Update to h1, t=1. Check if h1 unseen: if unseen, record time1, update to h2, t=2... Suppose at some step t=k, cur = h_k (which we will check before recording). At start of iteration with t=k, cur = h_k? Actually after updating, t becomes new value, and cur is the new state. Then we check if firstSeen[cur] is -1. If yes, we record for that cur (which is at time t). So we record times as we process each state at the moment we first see it. So after the last successful iteration, we recorded time for some state at time t. Then we update to next state, t increments, and we check that new state. If that new state is already seen, we exit without recording it. Therefore, the set of recorded times is from 0 up to the time of the last recorded state, which is t-1? Let's do small example to avoid confusion.
Better approach: We can simulate up to the point when we find a repeat and then break, and we can record occurrences along the way. We'll keep a vector of times when we encounter a_i. But we need also to determine if a_i is in the cycle or only in tail.
We can compute:
- t = 0, cur = start.
- while true: if cur == a_i: record time t. if visited[cur] != -1: pre_start = visited[cur] // first time this state seen cycle_start_time = pre_start cycle_len = t - pre_start break visited[cur] = t cur = (x*cur + y) % m t++
Here visited[cur] records the time when we first saw cur. At the moment we detect a repeat, we have cur that was seen before at time pre_start. At time t, we are about to process cur? Actually we have just computed cur as next state after processing at time t? Let's design careful:
Initialize visited array with -1. t = 0 cur = h_i while true: if cur == a_i: occurrences.append(t) if visited[cur] != -1: // This state was seen before at visited[cur] mu = visited[cur] // start of cycle (first time this state appeared) lambda = t - mu break visited[cur] = t // compute next cur = (x_i * cur + y_i) % m t++
Check: At t=0, cur is initial. We check if it's target, then check if visited[cur] != -1? Initially visited[cur] = -1, so not visited. Then we set visited[cur]=0, compute next cur, t becomes 1. Loop again.
Now suppose at some iteration, t = k, cur = some state s. If s was visited before at time mu, then we detect repeat. At that moment, we have not set visited[s] for this visit, we are just detecting. The current time is k, and we have not yet recorded the occurrence of target at time k? Actually we did: before checking visited, we did if cur == a_i, so we recorded occurrence at time k (this is the repeat occurrence). That's correct; we record that a_i occurs at this time as well. But careful: This repeat occurrence at time k is actually the second occurrence of state s. So if a_i equals s, then it appears again at time k. So we need to record that. That's fine.
Then we break, having mu = first time s was seen, and lambda = k - mu.
Now we have:
- visited times for all distinct states encountered before the repeat, including the first occurrence of s at time mu.
- We have recorded all times (including possibly at time mu, and at time k) when cur == a_i.
Now we need to classify whether a_i is in tail or cycle.
We have mu: the first time the repeated state (which is the entry point to the cycle) occurred. The cycle consists of states from time mu to time k-1 inclusive? Actually the cycle includes the state at mu, and then the sequence from mu+1 to k-1, and then at time k we are back to state s (the same as at mu). So the cycle length lambda = k - mu. The cycle states are those at times mu, mu+1, ..., mu+lambda-1 (since time mu+lambda = k equals mu state). So the cycle is the set of states visited from mu to k-1. So all states in that set are distinct and form a cycle.
Now a_i could be among these states (cycle) or among states before mu (tail). Since we recorded occurrences, we can determine:
- If there is an occurrence at time < mu: then a_i is in tail (only that occurrence, and possibly not in cycle because tail and cycle disjoint). But could a_i appear again later? If a_i is in tail and equals some state that later appears in cycle? That would mean that a_i state appears both in tail and cycle, which as argued impossible. But we should check: If a_i appears at time < mu, then it cannot appear at time >= mu because then it would be a repeat of that state, and then mu would be <= that earlier time. Actually if a_i appears at time t0 < mu and later at time t1 >= mu, then at time t1 we have a repeat of a_i, which would have been detected earlier? But our detection uses the first repeat: we break when we see a state that was seen before. The first repeat is the state at time t1 that equals a state seen earlier. If that earlier state is a_i at time t0, then mu would be t0, because that's the first time that state appeared. So mu would be t0, not the actual cycle entry we computed? Actually in the detection algorithm, we set mu = visited[cur] when we see cur again. So if a_i appears at t0 and later at t1, then at time t1 cur = a_i and visited[cur] = t0, so mu = t0. That means the cycle start is t0. So then a_i is part of the cycle (since it's at the start). And the occurrence at t0 is considered in the cycle (since cycle starts at mu = t0). So if a_i appears in tail and also later, then it's actually the cycle start, and the tail is before t0. So there would be no occurrence strictly before mu? Actually mu would be t0, so t0 is the start of the cycle, not tail. So occurrences at time t0 is in cycle. So we cannot have a_i in tail and also in cycle. So classification is: if the smallest occurrence time of a_i is less than mu, then a_i is only in tail (since it's not in cycle). If the smallest occurrence time is >= mu, then a_i is in cycle (and possibly appears multiple times after). However, it could be that a_i never appears. Then we treat as not reached.
But note: a_i could appear multiple times in the cycle? As argued, since cycle states are distinct, it can appear at most once per cycle. However, we may have recorded two occurrences: one at mu (if a_i is the cycle entry state) and one at mu+lambda (the repeat). But those are two times, but they are both in the cycle and separated by lambda. So that's fine; it appears at times mu + s + k*lambda. So we need to capture the first occurrence time in the cycle (the smallest t >= mu where a_i occurs). That is the first time it appears in the cycle (maybe at mu or later). We'll denote that as first_i_cycle (which is the first occurrence time that is >= mu). That is also the minimal t overall if there is no tail occurrence.
Now, if there is a tail occurrence at time t_tail < mu, then that is the only occurrence. Because if later it appeared again, mu would be t_tail as argued.
Thus we can compute:
- mu: cycle start time.
- lambda: cycle length.
- first_occurrence: the minimal t where a_i occurred (if any). Also record if it occurs later in cycle? we can compute first_in_cycle = None. We can check after simulation: if a_i was seen at any time t >= mu, then it's in cycle, and the smallest such t is first_in_cycle. But careful: if a_i appears exactly at mu, then it's in cycle. If it appears only at times < mu, then it's only in tail.
But we need to also consider the case where a_i never appears: then T_i is empty.
Now we also need to consider the possibility that the sequence never enters a cycle? But it's a finite state space, so it must eventually repeat. So cycle detection will always happen within at most m+1 steps.
Given that m <= 1e6, simulation up to at most m+1 steps per sequence is fine.
Now, we have for each sequence:
Case A: No occurrence of a_i => answer -1.
Case B: Occurrence only in tail at time t_single. Then T_i = {t_single}.
Case C: Occurrence in cycle (i.e., at least one occurrence at time >= mu). Then we have:
- first_i = smallest t where a_i occurs (which is >= mu).
- cycle_start = mu
- cycle_len = lambda Note that it's possible that a_i appears multiple times in the cycle? It can only appear once per cycle, because cycle states are distinct. But we might have recorded it twice (at first cycle occurrence and at the next cycle after lambda steps). Those are both >= mu and are separated by lambda. So the set of times is {first_i + k * lambda | k >= 0}. Also we must confirm that first_i - mu < lambda, which is true.
Now, but is it guaranteed that the first occurrence in the cycle is exactly at some offset s, and then repeats every lambda? Yes because after entering the cycle, the sequence is purely periodic with period lambda from mu onward. So if a_i is in the cycle, then for all t >= mu, h_i(t) = a_i iff t = mu + s (mod lambda), where s is the offset such that h_i(mu+s)=a_i. Since the cycle states are distinct, there is exactly one s. So the progression is as described.
Edge Cases: If lambda = 0? Cycle length at least 1.
Now, with these, we can compute answer.
Now we need to handle the two sequences.
Case B+B: both single times. Compare.
Case B+C: one single time t1, other progression. Check if t1 >= first2 and (t1 - first2) % lambda2 == 0. If yes, answer t1. Also ensure that t1 is within the cycle? Actually if t1 < first2, then progression hasn't started, so can't match. But if t1 equals first2, it's fine. Also need to consider if the progression includes times before first2? The progression is defined as t = first2 + k*lambda2, k>=0, so t >= first2. So if t1 < first2, not included. So condition as above.
But what if the progression's cycle hasn't started yet? Actually if first2 >= mu2, that's fine. But could there be case where t1 is before mu2? Since mu2 <= first2? Actually first2 is the first occurrence in the cycle, which is >= mu2. So t1 < mu2 is also < first2. So not in progression.
Case C+C: both progressions.
We need to find smallest t >= max(first1, first2) satisfying t ≡ first1 (mod λ1) and t ≡ first2 (mod λ2). But also need to consider that t must be at least the cycle start times? Actually the progression holds for all t >= first_i. Since first_i >= mu_i, it's fine. However, there is nuance: The progression representation t = first_i + k_i*λ_i holds for all k_i >= 0. However, is it possible that there exists t that is less than first_i but still satisfies the congruence? For example, suppose first_i = 10, λ_i = 5. Then t = 5 satisfies t ≡ 10 mod 5? 5 mod 5 = 0, 10 mod 5 = 0, so t=5 ≡ first_i (mod λ_i) but t=5 < first_i. But does t=5 correspond to a time when h_i = a_i? At time 5, maybe h_i is not a_i because the first occurrence is at time 10. Because the progression only starts at first_i; the sequence before that (preperiod) does not have the target. So t=5 is not valid. So we must enforce t >= first_i. So CRT solution must account for lower bounds.
Thus we solve: t = first1 + λ1 * x, t = first2 + λ2 * y, with x,y >= 0 integers. Find minimal t.
We can rewrite as t ≡ r1 (mod λ1) where r1 = first1 % λ1. Similarly r2 = first2 % λ2. But with constraint t >= max(first1, first2).
Standard method: solve the congruence:
t ≡ first1 (mod λ1) t ≡ first2 (mod λ2)
Let d = gcd(λ1, λ2). If (first2 - first1) % d != 0 => no solution.
Otherwise, we can compute a solution t0 modulo L = lcm(λ1, λ2) using extended Euclidean. The general solution is t = t0 + k * L, for integer k.
Now we need the smallest t >= lower = max(first1, first2). So we can compute t = t0 + kL where k is such that t >= lower. That's straightforward: k = ceil((lower - t0) / L) if t0 < lower, else k=0. Then t = t0 + kL. But need to ensure that t0 is a valid solution that satisfies the congruences and also corresponds to x,y >=0? Actually if t satisfies the congruences and t >= max(first1, first2), then automatically x = (t - first1)/λ1 >=0 and y = (t - first2)/λ2 >=0, because t >= first1 and t >= first2. So that condition is sufficient.
But careful: The congruence solution t0 might be negative or less than both first_i. However, adding multiples of L yields all solutions. So we find the smallest non-negative? But we need the smallest that is >= lower.
But is it guaranteed that for such t, the corresponding x,y are integers? Yes, because t ≡ first1 mod λ1 ensures (t - first1) divisible by λ1. Since t >= first1, division yields non-negative integer.
Thus we can compute.
Now we also need to consider the scenario where one or both sequences have the target only in the tail, but we might have multiple occurrences? As argued, only one. But wait: Could the target appear in the tail and also in the cycle? As argued, not possible because then tail and cycle would intersect. So only one occurrence.
Thus algorithm:
For each sequence i (i=1,2):
-
Simulate using visited array to detect cycle and record occurrences of a_i.
-
After detection, we have:
- mu_i = cycle_start (time when first state in cycle first appeared)
- lambda_i = cycle_len
- occ_times: list of times when a_i seen (we recorded as we went). We'll have them in order. But careful: During simulation, we might have recorded occurrence at time mu_i (if a_i is the cycle entry) and also at later time (mu_i + lambda_i) which is the repeat detection time. But our simulation stops at the repeat detection time, and we recorded that occurrence as well (since we check before breaking). So occ_times includes all occurrences up to the repeat detection time inclusive. However, after the break, we don't simulate further, but we know that from then on it repeats with period lambda_i, so if a_i is in cycle, it will occur again every lambda_i after the first occurrence. But we only need the first occurrence in the cycle.
To classify:
-
If occ_times is empty => no occurrence. Set type = none.
-
Else, find the minimum time t_min among occ_times. If t_min < mu_i => then target appears only in tail, and because of disjointness, there should be no other occurrence >= mu_i. But we should verify: Could there be another occurrence at time >= mu_i? If there is, then that would mean a_i appears again, which would cause mu_i to be <= t_min? Let's test: Suppose a_i appears at time t0 < mu_i, and later appears at time t1 >= mu_i. Then at time t1, cur = a_i, and visited[a_i] = t0 (since first occurrence at t0). Then when we detect repeat, we would have break at time t1, and set mu = visited[cur] = t0, and lambda = t1 - t0. So mu would be t0, not the previously computed mu_i? Actually our detection algorithm sets mu = visited[cur] at the time we first see a repeat. That repeat is the first time we encounter a state that was visited before. So if a_i appears at t0 and again at t1, then when we get to time t1, we detect cur = a_i, visited[a_i] = t0, so mu = t0, lambda = t1 - t0. Therefore, mu_i would be t0, not something else. Thus t0 would be considered the start of the cycle, not a tail. So in that scenario, t_min = t0, but t0 would be mu_i, not less than mu_i. So the case t_min < mu_i can only happen if a_i appears only once and that time is before the cycle start (i.e., not part of the cycle). So we can trust that if t_min < mu_i, then there is no other occurrence (since any later occurrence would cause mu_i to be t_min). So it's safe.
-
If occ_times nonempty and t_min >= mu_i, then target is in cycle. Then first_i_cycle = min(occ_times) which is >= mu_i. Also note that occ_times may include times > mu_i+lambda_i? Actually our simulation only runs until the repeat detection, so we have at most two occurrences: one at first time in cycle (maybe mu_i or later) and one at the repeat time (mu_i + lambda_i). Both are >= mu_i. The minimal is the first. So we set first_i = t_min.
-
Also if occ_times empty, type = none.
For cycle case, we also need lambda_i. But note: lambda_i is the cycle length. However, careful: The cycle length might be 0? No, at least 1.
But there is an edge: If the sequence becomes constant? That is cycle of length 1. That's fine.
Now we have for each sequence: type (none, tail, cycle) and data:
- tail: time t_tail.
- cycle: first occurrence t_first, cycle start mu (though not needed directly), cycle length L.
Now compute answer.
Implementation steps:
- Read m.
- Read h1, a1.
- Read x1, y1.
- Read h2, a2.
- Read x2, y2.
Define function process(h, a, x, y, m): visited = array of size m initialized to -1. occurrences = [] (or we can record min_time, but also need to know if there is any occurrence after mu) t = 0 cur = h while True: if cur == a: occurrences.append(t) if visited[cur] != -1: mu = visited[cur] lam = t - mu break visited[cur] = t cur = (x * cur + y) % m t += 1
After break, we have mu, lam, occurrences.
if occurrences is empty: return (type='none') else: t_min = min(occurrences) if t_min < mu: # only tail # But need to confirm there is no later occurrence? Could there be later occurrence that we missed because we broke before it? We captured up to t (the repeat detection time). If the only occurrence is before mu and there is another after mu, that would have caused mu to be t_min as argued. So safe. return (type='tail', time=t_min) else: # in cycle # first occurrence in cycle is t_min (which is >= mu) # However, ensure that the progression is indeed t_min + klam. Because from mu onward, period is lam. But we need to confirm that t_min is within the cycle and that the offset from mu is s = t_min - mu, and indeed for all k, at time mu + s + klam, we get a. That's true because the cycle repeats exactly. # Also note: Could t_min be > mu + lam? No, t_min is <= mu+lam-1? Actually t_min could be mu+lam? That would be the repeat detection time (t). At time t (when we break), we have cur = state that was first seen at mu, so time t = mu+lam. At that time we recorded occurrence if cur == a. So t_min could be mu+lam if a equals the cycle entry state? Let's see: If a is the cycle entry state (the state that repeats), then first occurrence in cycle might be at time mu (the first time that state appears) and also at time mu+lam (the repeat). So t_min would be mu, not mu+lam. So t_min is at most mu+lam-1? Actually the repeat detection time t equals mu+lam. At that time, cur equals state at mu. So if a equals that state, we would have recorded occurrence at time mu (when we first visited it) and also at time t. So the smallest is mu. So t_min is always < mu+lam? It could be mu+lam if the first occurrence in cycle is exactly at the repeat detection time and we didn't record it earlier? But that would mean that the state a is not visited in the cycle before the repeat, but appears exactly at time t. But the cycle consists of times mu, mu+1, ..., mu+lam-1. The state at time mu+lam is the same as state at mu, so it is part of the cycle but time mu+lam is equivalent to mu modulo lam (with shift). However, strictly speaking, the cycle periodicity says for all t >= mu, h(t) = h(t+lam). So if a appears at time mu+lam, then by periodicity it also appears at time mu (since h(mu)=h(mu+lam)). But if we didn't record it at time mu because maybe we didn't see it? Wait, our simulation recorded occurrences up to time t (the detection time) inclusive. At time mu, we recorded visited[state] = mu, and also if state == a, we recorded occurrence. So if a equals the cycle entry state, we would have recorded at mu. So t_min would be mu, not mu+lam. So t_min is always < mu+lam. So it's fine. # So first occurrence in cycle is t_min. return (type='cycle', first=t_min, lam=lam)
However, one more nuance: The simulation may have broken before we have seen the entire cycle? We have seen exactly one full cycle: from mu to mu+lam-1 are distinct states; at time mu+lam we get the repeat. So we have observed all states in the cycle. So if a is in the cycle, we would have recorded it at some time between mu and mu+lam-1 inclusive. So t_min is within [mu, mu+lam-1]. So good.
Now after processing both sequences, compute answer.
But we need to be careful: The "cycle" case: first occurrence time is t_first. But does the progression include all times t_first + klam for any k >= 0? Yes, because for any integer k >= 0, time t = t_first + klam >= t_first, and since the sequence is periodic from mu onward, and t_first is within one cycle, we have h(t) = a. However, we must ensure that t_first + k*lam is >= mu? Actually if k is 0, t_first >= mu by definition. For k>0, t >= t_first + lam >= mu+? Possibly still >= mu. So all times are valid.
Now case C+C: solving CRT.
But there is a nuance: The periodicity holds for all t >= mu, but t_first is the first time in the cycle when a appears. However, could there be a time earlier than t_first but still >= mu that gives a? No, because within one cycle, a appears exactly once. So the set of t >= mu such that h(t)=a is exactly {t_first + k*lam | k >= 0}. But what about times before mu? Not in cycle, and if a is not in tail, there are none.
Thus correct.
Now we need to compute CRT. Since λ1 and λ2 can be up to m (1e6) and product up to 1e12, lcm can be as high as 1e12 (but may be larger if both are up to 1e6, lcm can be up to about 1e12, which fits in 64-bit (since 1e6*1e6=1e12 exactly, fits in 64-bit signed? 1e12 < 2^63 ~9e18, so fine). But we need to compute lcm carefully to avoid overflow beyond 64-bit? 1e6 * 1e6 = 1e12, fits in 64-bit. But if m=1e6, cycle lengths can be up to m, so lcm <= 1e12, safe.
We also need to compute solution t0 modulo L using extended gcd. We'll implement a function to solve:
Given a1, n1, a2, n2, we want t ≡ a1 (mod n1), t ≡ a2 (mod n2), with t >= max(a
-