컴퓨터 캐시

컴퓨터에는 1번부터 n번까지 번호가 붙은 n개의 주소로 이루어진 캐시가 있다. 각 주소에는 1바이트를 저장한다. 처음에 캐시의 모든 바이트는 0이다.

저장하려는 m개의 데이터가 있다. 각 데이터는 바이트 배열이다. 데이터의 길이는 서로 다를 수 있고, 같은 데이터를 여러 위치에 저장할 수 있다.

컴퓨터에서 q개의 연산을 수행한다. 연산은 세 종류다.

• 1 i p: 캐시의 p번 위치부터 i번 데이터를 적재한다. 이때 캐시에 이미 저장되어 있던 값은 덮어쓴다. 이 연산은 항상 유효하다(데이터가 캐시의 끝을 넘지 않는다). 같은 데이터의 여러 버전이 캐시의 여러 위치에 동시에 적재되어 있을 수 있다.
• 2 p: 캐시의 p번 주소에 저장된 바이트를 출력한다.
• 3 i l r: i번 데이터의 l번째부터 r번째 바이트까지 1씩 증가시킨다. 바이트이므로 256으로 나눈 나머지를 취한다. 이 연산은 캐시에 이미 적재된 값에는 영향을 주지 않는다. 데이터에만 영향을 주며, 이후에 그 데이터를 적재할 때 반영된다.

첫째 줄에 세 정수 n, m, q가 주어진다(1 ≤ n, m, q ≤ 5 ∙ 105). n은 컴퓨터 캐시의 크기, m은 데이터의 개수, q는 연산의 개수다.

다음 m개 줄에 각각 하나의 데이터가 공백으로 구분된 정수의 나열로 주어진다. 줄의 첫 정수 ki (1 ≤ ki, ∑ki ≤ 5 ∙ 105)는 뒤따르는 정수의 개수를 나타낸다. 이어지는 ki개의 정수 x (0 ≤ x ≤ 255)는 데이터의 내용이다.

다음 q개 줄에 연산을 나타내는 두 개, 세 개 또는 네 개의 정수가 공백으로 구분되어 위에서 설명한 순서대로 주어진다. 다음 중 하나다.

1 i p 또는 2 p 또는 3 i l r

(1 ≤ i ≤ m), (1 ≤ p ≤ n), (1 ≤ l ≤ r ≤ ki)이다. 2번 연산이 적어도 하나 주어진다.

각 2번 연산마다 캐시 p번 위치의 정숫값을 한 줄에 하나씩 출력한다.