Redstone Clock¶

Indicative time limit: 3.0 seconds (reference environment: environment and measurements)
Actual time limit: twice the reference program's baseline time on the slowest official test file in the target environment, rounded up to a multiple of 0.5 seconds; round up further if the platform requires a coarser unit.
Memory limit: 512 MB

Story¶

The village chief is building a redstone alarm for long delays. Two clocks start together, and the alarm rings whenever both finish a cycle simultaneously. Test a sequence of generated period pairs and summarize the first ringing time for each pair.

Formal Problem Statement¶

Given positive integers \(n,a\) , perform \(2n\) queries. Two clocks with periods \(s,t\) start at time \(0\) . Their query answer is the first positive time when both finish a cycle; time \(0\) is excluded.

Let \(U=10000000\) . For \(i=1,\ldots,n\) , carry out these steps in order:

Query periods \(i,a\) for query \(2i-1\) and record the answer.
Set \(a\gets(a+10007)\bmod U+1\) .
Query periods \(i,a\) for query \(2i\) and record the answer.
Set \(a\gets(a^2+1)\bmod U+1\) .

Output the bitwise XOR of answers to odd-numbered queries, followed by the bitwise XOR of answers to even-numbered queries.

Input Format¶

Read two integers \(n,a\) on one line, where \(a\) is the initial value.

Output Format¶

Print two lines: the XOR of odd-query answers, then the XOR of even-query answers.

Sample 1¶

Input¶

5 7

Output¶

8312897
24761077

Explanation¶

Generate ten queries in the specified order. Each updated value of \(a\) is used by the next query.

Sample 2¶

Input¶

1 1

Output¶

1
10009

Explanation¶

The first periods are \(1,1\) , so the answer is \(1\) . Updating \(a\) gives \(10009\) , which is the answer to the second query with period \(1\) .

Constraints and Guarantees¶

\(1\le n\le10000000\) and \(1\le a\le10000000\) .

Test Groups¶

Score share	Additional conditions
25%	\(n\le1000000\)
75%	No additional conditions