Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Revisiting Metro Rail Blocks

By jackal_1586 · 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.

Discussion

Statistics


53% Solution Ratio

EgorKulikovEarliest, 3w ago

avijit_agarwalFastest, 0.6s

hp1999Lightest, 131 kB

kzvd4729Shortest, 339B

Submit

Login to submit

Related Contests

Criterion 2020 Round 4 Ended at 2020-03-13 11:30:00 +0000 UTC