Hide

Problem G
Gux's sequence

Gux really likes to play with sequences. He has a big sequence of length $n$, indexed from $1$ to $n$. Initially, all elements in the big sequence are zero. Gux also has $m$ mini-sequences that may have different lengths. These mini sequences are numbered from $1$ to $m$, where the $i^{th}$ mini-sequence has length $k_ i$. The elements of each mini-sequence are also numbered starting from $1$.

Gux will process $q$ queries, there are 3 types of queries:

  • 1 $x$ $p$ Copy the entire $x^{th}$ mini sequence into the big sequence, starting from position $p$. It is guaranteed that the entire mini sequence will fit in the big sequence. In other words, do the following operation:

    // guaranteed that p+k_i-1 <= n
    for i from 1 to k_i:
        big[p+i-1] = mini_x[i]
    
  • 2 $p$ Print the value of the $p^{th}$ element of the big sequence.

  • 3 $l$ $r$ $x$ Increase all elements from index $l^{th}$ to $r^{th}$ of the $i^{th}$ mini sequence by $1$, modulo $256$.

Input

Note: Please note that the input will be given in a special format. Denote $last$ as the answer of the most recent 2nd type query. This variable will be updated after every 2nd type query is answered.

The first line of input contains three integers $n$, $m$, $q$ ($ 1 \leq n,m,q \leq 5 \cdot 10^5$).

Each of the following $m$ lines contains a mini sequence. Each sequence will start with a number $k_ i$ ($1 \leq k_ i \leq n$) - the length of this mini sequence. After that, $k_ i$ integers $x$ ($0 \leq x \leq 255$) will follow. It’s guaranteed that the sum of all $k_ i$ will not exceed $5 \cdot 10^5$.

Each of the next $q$ lines will contain one of the three types of queries:

  • $1$ $x_{raw}$ $p_{raw}$. The actual query will be $1$ $x$ $p$ where $x = x_{raw} \oplus last$ and $p = p_{raw} \oplus last$. ($1 \leq x \leq m$, $ 1 \leq p \leq p+k_ i-1 \leq n$)

  • $2$ $p_{raw}$. The actual query will be $2$ $p$ where $p = p_{raw} \oplus last$. ($ 1 \leq p \leq n$). Please note that after each query of this type, $last$ must be updated.

  • $3$ $x_{raw}$ $l_{raw}$ $r_{raw}$. The actual query will be $3$ $x$ $l$ $r$ where $x = x_{raw} \oplus last$, $l = l_{raw} \oplus last$, $r = r_{raw} \oplus last$. ($1 \leq x \leq m$, $1 \leq l \leq r \leq k_ i$).

All raw variables will have values between $0$ and $10^9$.

Output

With each query of the 2nd type, print one integer on a newline - the answer for that query.

Explanation of Sample Input 1

Without any special encoding, the input is:

6 2 6
3 255 123 0
4 6 7 9 254
3 1 1 3
1 1 2
2 3
1 2 3
2 2
2 6
Sample Input 1 Sample Output 1
6 2 6
3 255 123 0
4 6 7 9 254
3 1 1 3
1 1 2
2 3
1 126 127
2 126
2 6
124
0
254
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Vuong Hoang Long
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in