구조물

바이트랜드에서 오래된 구조물의 복원 공사가 시작되었다. 공사는 앞으로도 여러 달이 걸리지만, 이미 많은 주민이 첫 방문을 위한 표를 사 두었다. 구조물이 견딜 수 있는 하중에는 한계가 있어서, 한 번에 몇 명이 올라갈 수 있는지는 아직 정해지지 않았다. 올라갈 사람은 표를 산 순서대로 줄의 맨 앞에서부터 뽑는다.

구조물은 매우 규칙적으로 지어진다. 먼저 짝수 개의 기둥을 바닥에 세운다. 이웃한 두 기둥마다 그 위에 판을 하나씩 얹고, 각 판 위에 새 기둥을 하나씩 세운다. 방금 세운 기둥들에 대해 같은 과정을 반복하여 층을 하나씩 위로 쌓아 올린다. 모든 층의 기둥 수는 짝수이므로 항상 다음 층을 지을 수 있다.

층은 위에서부터 번호를 매긴다. 맨 위층이 $1$층이고 기둥이 $2$개, $2$층은 기둥이 $4$개이며, 일반적으로 $i$층에는 기둥이 $2^i$개, 맨 아래 $n$층에는 기둥이 $2^n$개 있다. $1$층의 두 기둥은 맨 꼭대기의 판 하나를 받치고 있으며, 사람들은 바로 그 판 위에 모인다.

각 기둥에는 견딜 수 있는 최대 하중인 강도가 정해져 있다. 판은 하중을 얼마든지 견딜 수 있고, 자기 위에 놓인 하중을 바로 아래 두 기둥에 항상 똑같이 나누어 전달한다. 판과 기둥의 무게는 무시한다.

복원가는 몇몇 기둥의 강도를 한 번에 하나씩 교체한다. 한 번 교체할 때마다, 개회식에서 구조물이 무게를 버틸 수 있는, 줄 맨 앞에서부터 뽑은 사람 수의 최댓값을 알고 싶어 한다.

첫째 줄에 세 정수 $n$, $m$, $k$ ($1 \le n \le 19$, $1 \le m, k \le 10^6$)가 주어진다. 각각 층 수, 표를 산 주민 수, 기둥 교체 횟수를 뜻한다.

다음 $n$개의 줄은 위층부터 아래층까지 각 층을 설명한다. 그중 $i$번째 줄은 $i$층을 설명하며 $2^i$개의 정수 $s_1, s_2, \dots, s_{2^i}$ ($1 \le s_j \le 10^9$)를 담는다. 여기서 $s_j$는 $i$층에서 왼쪽에서 $j$번째 기둥의 강도이다. 따라서 각 줄에는 차례로 $2, 4, 8, \dots, 2^n$개의 정수가 있다.

그다음 줄에는 $m$개의 정수 $w_1, w_2, \dots, w_m$ ($1 \le w_i \le 10^9$)이 주어지며, $w_i$는 $i$번째로 표를 산 사람의 무게이다.

이어지는 $k$개의 줄은 각각 하나의 교체를 뜻하며 세 정수 $x$, $y$, $p$ ($1 \le x \le n$, $1 \le y \le 2^x$, $1 \le p \le 10^9$)로 이루어진다. $x$층에서 왼쪽에서 $y$번째 기둥의 강도가 $p$로 바뀐다.

$k + 1$개의 줄을 출력한다. $t = 0, 1, \dots, k$에 대해 $t$번째 줄에는 정수 하나를 출력하며, 이는 처음 $t$번의 교체를 적용한 뒤 구조물이 버틸 수 있는, 줄 맨 앞에서부터 뽑은 사람 수의 최댓값이다. 첫 줄은 아무 교체도 하지 않은 상태의 답이다.