Computer Cache

Time limit5sMemory limit512 MB

Summary
Maintain a mutable byte array over m pieces, support range increments modulo 256 on a piece, cache loads of whole pieces into fixed cache positions, and point queries of cache bytes.
Level

Hard8 of 10

Topics
Segment tree, Array, Linked list, Implementation
Solved
No attempts yet

Problem

Your computer has a cache made of n addresses, numbered 1 to n. Each address holds one byte. Initially every byte in the cache is zero.

You have m pieces of data to store. Each piece of data is a byte array. The pieces can have different lengths, and the same piece can be stored at several locations.

You will perform q operations on the computer. There are three types of operations:

  • 1 i p: Load piece of data i starting at position p of the cache. This overwrites whatever was stored in the cache before. The operation is always valid (the data never goes past the end of the cache). Several versions of a piece of data can be loaded at different positions of the cache at the same time.
  • 2 p: Print the byte stored at address p of the cache.
  • 3 i l r: Increment bytes l through r of piece of data i by 1. These are bytes, so the increment is taken modulo 256. This does not affect values already loaded in the cache. It only affects the piece of data itself and any future loads of that piece.

Input

The first line contains three integers n, m and q (1 ≤ n, m, q ≤ 5 ∙ 105), where n is the size of the cache, m is the number of pieces of data, and q is the number of operations.

Each of the next m lines describes one piece of data as a sequence of space-separated integers. The first integer on the line, ki (1 ≤ ki, ∑ki ≤ 5 ∙ 105), is the number of integers that follow. The next ki integers x (0 ≤ x ≤ 255) are the contents of the piece of data.

Each of the next q lines contains two, three, or four space-separated integers describing an operation, in the order given above. It is one of:

1 i p or 2 p or 3 i l r

with (1 ≤ i ≤ m), (1 ≤ p ≤ n), and (1 ≤ l ≤ r ≤ ki). At least one operation of type 2 is given.

Output

For each operation of type 2, print the integer value of cache location p, one per line.

Examples1

  1. Example 1

    Input
    5 2 10
3 255 0 15
4 1 2 1 3
2 1
1 2 2
1 1 1
2 1
2 4
3 1 1 2
2 1
1 1 2
2 2
2 5
    Expected output
    0
255
1
255
0
3