8683번 - Budowla 다국어

W Bajtocji ruszyła rekonstrukcja dawnej budowli. Mimo że budowa potrwa jeszcze wiele miesięcy, to bilety, na pierwszą wizytę wykupiło już wielu mieszkańców. Nie wiadomo jeszcze, ile osób będzie w stanie przebywać w budowli w jednym czasie ze względu na ograniczenia wytrzymałościowe. Będzie to pewna liczba pierwszych w kolejności osób, które wykupiły bilety.

Budowla została zbudowana w specyficzny sposób. W pierwszej kolejności ułożono pewną parzystą liczbę słupów. Następnie na kolejne pary słupów położono płytę. Później na każdej płycie stawiano jeden słup. Następnie ponowiono proces układania płyt - na kolejnych dwóch słupach leżących na płytach najwyższego piętra układano płyty z pojedynczym słupem i tak powstawały kolejne piętra. Projekt był tak zaplanowany, aby na każdym piętrze była parzysta liczba słupów, więc zawsze dawało się zbudować kolejne piętra. Każdy słup ma określoną wytrzymałość, czyli maksymalne obciążenie, jakie może utrzymać.

Uroczyste otwarcie odbędzie się na szczycie budowli, na której zgromadzi się pewna liczba mieszkańców Bajtocji. Łącznie stworzą dość duże obciążenie, równe ich łącznej wadze. Wiadomo, że obciążenie rozkłada się zawsze równomiernie na dwa słupy, podtrzymujące płytę, oraz że płyty mogą wytrzymać dowolne obciążenie.

Rekonstruktor postanowił wymienić pewną liczbę słupów. Po każdej wymianie jednego słupa chciałby wiedzieć, ile maksymalnie osób z kolejki będzie mogło wziąć udział w uroczystym otwarciu. Zakładamy, że waga płyt i słupów jest pomijalnie mała.

Pierwszy wiersz standardowego wejścia zawiera trzy liczby całkowite n, m, k (1 ≤ n ≤ 19, 1 ≤ m, k ≤ 10⁶), oznaczające odpowiednio liczbę pięter budowli, liczbę mieszkańców Bajtocji, którzy wykupili już bilety oraz liczbę słupów do wymiany.

Kolejne n wierszy zawiera opisy poszczególnych pięter od najwyższego do najniższego. Kolejne wiersze zawierają 2, 4, 8, ..., 2ⁿ liczb całkowitych. W każdym wierszu znajduje się więc 2ⁱ liczb całkowitych s₁, s₂, ..., s_2ⁱ (1 ≤ s_k ≤ 10⁹), gdzie s_k jest wytrzymałością k-tego w kolejności (od lewej) słupa na i-tym piętrze (od góry).

W następnym wierszu znajduje się m liczb całkowitych w₁, w₂, ..., w_m (1 ≤ w_i ≤ 10⁹), gdzie w_i oznacza wagę osoby, która jako i-ta kupiła bilet.

Kolejne k wierszy opisuje wymieniane słupy. Każdy wiersz zawiera trzy liczby całkowite x_i, y_i, p_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2^x_i, 1 ≤ p_i ≤ 10⁹), oznaczające, że wytrzymałość słupa y_i (od lewej) na piętrze x_i (od góry) zostaje zamieniona na wytrzymałość p_i.

Standardowe wyjście powinno zawierać s + 1 wierszy. W kolejnych wierszach powinna znaleźć się jedna liczba całkowita, równa maksymalnej liczbie osób z kolejki, która może wziąć udział w uroczystym otwarciu po wymianie 0, 1, 2, ..., s słupów.