CSES 3426 ↗

Sliding Window Xor

The bitwise xor of each window of `k` elements; print the xor of those values. The array is produced by the linear generator in the input.

1
submissions
1.000
best score

You are given an array of n integers. Your task is to calculate the bitwise xor of each window of k elements, from left to right.

In this problem the input data is large and it is created using a generator.

Input

The first line contains two integers n and k: the number of elements and the size of the window.

The next line contains four integers x, a, b and c: the input generator parameters. The input is generated as follows:

  • x1=x
  • xi=(axi−1+b) mod c for i=2,3,…,n

Output

Print the xor of all window xors.

Constraints

  • 1≤k≤n≤107
  • 0≤x,a,b≤109
  • 1≤c≤109

Example

Input:

8 5
3 7 1 11

Output:

0

Explanation: The input array is [3,0,1,8,2,4,7,6]. The windows are [3,0,1,8,2], [0,1,8,2,4], [1,8,2,4,7] and [8,2,4,7,6], and their xors are 8, 15, 8 and 15. Thus, the answer is 8⊕15⊕8⊕15=0.

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/SlidingWindowXor/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
390,007,016390,007,016

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.000390,007,016talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 14:37 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.