Revisiting Metro Rail Blocks

jackal_1586 Criterion 2020 Round 4
Limits 3s, 512 MB

The city of Dhaka is experiencing the construction of metro rails. Imagine one such metro rail spans from Gulshan to Mirpur. There will be N blocks in total that will serve as the holding structure for the rail lines. The first block is numbered as 1 and the final block is numbered as N. Construction process is fast and each day, one block is being created. But there is a problem.

The blocks are not constructed sequentially. For example, if N=5, the blocks can be created in the following order: 2,4,5,3,1. Since the orders are random, the construction company wants to keep track of the progress properly. They want to measure how many contiguous blocks are created from the start after each day's work.

You will be given the order of blocks in which they are going to be constructed. You have to answer after each day, maximum size of contiguous blocks that are made from the start. The first block is identified as 1.

For this problem, you need an integer N and a permutation of 1 to N as an array A of size N. the ith integer represents the block constructed on ith day. Since N can be very big, we will provide two integers g and N.
Then you will construct the array as Ai = gi-1 mod (N+1), where (1 ≤ i ≤ N).

Input

There will be two integers g and N as input.

  • 3 ≤ N ≤ 100000000
  • 2 ≤ g < N

Output

Calculate N integers. The ith integer indicates the number of contiguous blocks are made from the start after the ith day. Now print the XOR value of these integers. If the integers are considered an array B1, B2, ... BN, then print (B1 xor B2 ... xor BN).

Samples

InputOutput
3 6
2
InputOutput
8 10
9

For the first sample, the array A = [1 3 2 6 4 5]

On the 1st day, Block 1 is built. So, the size from the start, B1 = 1.

On the 2nd day, Block 3 is built. So, the size from the start, B2 = 1. (1 and 3 are not connected)

On the 3rd day, Block 2 is built. B3 = 3.

On the 4th day, Block 6 is built. B4 = 3.

On the 5th day, Block 4 is built. B5 = 4.

On the 6th day, Block 5 is built. B6 = 6.

So, the XOR of all the values is 2.

Submit

Login to submit.

Statistics

54% Solution Ratio
EgorKulikovEarliest, Mar '20
avijit_agarwalFastest, 0.6s
hp1999Lightest, 131 kB
kzvd4729Shortest, 339B
Toph uses cookies. By continuing you agree to our Cookie Policy.