Card Shuffling Math Game

Uncle Fang has some blank playing cards and wants to play a mathematical game with them. He will form m decks of cards. The process is as follows:

Deck 0

1. He chooses a positive integer n₀ and forms deck 0 with exactly \(2^{n_0}\) cards. The cards are initially labeled in increasing order from 1 to \(2^{n_0}\).
2. He decides to perform \(x_0\) shuffles. Each shuffle is executed with the following fixed routine:
   1. Extract the cards in the odd positions (1-indexed) in order to form a new deck.
   2. Place this new deck in front of the remaining cards (which are in the even positions, in order).
   For example, if \(n_0=3\), the deck initially is 1 2 3 4 5 6 7 8, after one shuffle it becomes 1 3 5 7 2 4 6 8, and after two shuffles it becomes 1 5 2 6 3 7 4 8.
3. After shuffling, he adds an integer \(t_0\) to every card in positions from \(l_0\) to \(r_0\) (inclusive). Then he computes the bitwise XOR of these modified numbers. The result modulo \(2^{n_0-1}\) is denoted as \(\mathrm{ans}_0\).

Decks 1 to m-1

For each deck \(i\) (with \(1 \le i \le m-1\)), the parameters are determined based on the result of the previous deck as follows:

• \(n_i = ((\mathrm{ans}_{i-1} + i - 1) \bmod 5) + \mathtt{base}\). Then deck \(i\) is formed with \(2^{n_i}\) cards, labeled from 1 to \(2^{n_i}\) in increasing order.
• \(l_i = ((2\mathrm{ans}_{i-1} + l_{i-1} + i - 1) \bmod 2^{n_i}) + 1\).
• \(r_i = \Bigl(\bigl(\mathrm{ans}_{i-1} + 1 + 2^{\lfloor n_i/2 \rfloor} \times (l_i \bmod 2^{\lfloor n_i/2 \rfloor})\bigr) \bmod 2^{n_i}\Bigr) + 1\).
• If \(l_i > r_i\), swap their values.
• \(x_i = (r_i - l_i + t_{i-1} + i - 1) \bmod 2^{n_i}\) indicates the number of shuffles to perform on deck \(i\).
• \(t_i = (l_i + r_i) \bmod 2^{n_i}\) is the number to be added to every card in positions \(l_i\) to \(r_i\) after shuffling.
• After shuffling deck \(i\) by the above routine \(x_i\) times, add \(t_i\) to each of the cards in positions \(l_i\) to \(r_i\) and compute their XOR. The value \(\mathrm{ans}_i\) is obtained by taking the XOR value modulo \(2^{n_i-1}\).

Your task is to compute \(\mathrm{ans}_{m-1}\) – the result of the last deck – before Uncle Fang finishes his game.

Input Format

The input consists of two lines:

• The first line contains two integers: m and base (a positive integer).
• The second line contains five integers: n0, x0, l0, r0, and t0 – the parameters for deck 0.

Output Format

Output a single integer: ansm-1, the final result of the game obtained from the last deck.

Note: All modulo operations are performed with powers of 2 as indicated in the formulas, and all positions are 1-indexed.

inputFormat

The first line contains two integers m and base.

The second line contains five integers: n0, x0, l0, r0, and t0, representing the parameters for deck 0.

outputFormat

Output a single integer ansm-1, which is the final result obtained from the last deck after performing the prescribed operations.

sample

1 3
3 1 2 5 3

1