There's a famous museum in the city where Kleofáš lives. In the museum, n exhibits (numbered 1 through n ) had been displayed for a long time; the i -th of those exhibits has value v i and mass w i . Then, the museum was bought by a large financial group and started to vary the exhibits. At about the same time, Kleofáš... gained interest in the museum, so to say. You should process q events of three types: type 1 — the museum displays an exhibit with value v and mass w ; the exhibit displayed in the i -th event of this type is numbered n + i (see sample explanation for more details) type 2 — the museum removes the exhibit with number x and stores it safely in its vault type 3 — Kleofáš visits the museum and wonders (for no important reason at all, of course): if there was a robbery and exhibits with total mass at most m were stolen, what would their maximum possible total value be? For each event of type 3, let s ( m ) be the maximum possible total value of stolen exhibits with total mass ≤ m . Formally, let D be the set of numbers of all exhibits that are currently displayed (so initially D = {1, ..., n}). Let P ( D ) be the set of all subsets of D and let Then, s ( m ) is defined as Compute s ( m ) for each . Note that the output follows a special format. The first line of the input contains two space-separated integers n and k ( 1 ≤ n ≤ 5000 , 1 ≤ k ≤ 1000 ) — the initial number of exhibits in the museum and the maximum interesting mass of stolen exhibits. Then, n lines follow. The i -th of them contains two space-separated positive integers v i and w i ( 1 ≤ v i ≤ 1 000 000 , 1 ≤ w i ≤ 1000 ) — the value and mass of the i -th exhibit. The next line contains a single integer q ( 1 ≤ q ≤ 30 000 ) — the number of events. Each of the next q lines contains the description of one event in the following format: 1 v w — an event of type 1, a new exhibit with value v and mass w has been added ( 1 ≤ v ≤ 1 000 000 , 1 ≤ w ≤ 1000 ) 2 x — an event of type 2, the ex