It's hard to see the scoreboard…

Your team has already finished the ECOO Provincials, but you aren't sure if you are winning or not!

A team's score on the ECOO is computed in a somewhat unorthodox manner. Each of the ~N~ problems, numbered from ~1~ to ~N~, is worth up to ~P~ points each. The contest is ~T~ minutes long, and for each submission to a problem, a team earns a time bonus of:

$$\displaystyle \left\lceil \frac{T-\text{submission time}} M \right\rceil$$

points if their submission earns a non-zero number of points, where ~M~ is a given integer number of minutes. ~\left\lceil x \right\rceil~ denotes the ceiling function, which returns the smallest integer that is greater than or equal to ~x~. To simplify, all teams will make up to one submission to each problem.

You are given the points earned and the submission times of each problem for your team and another team. Your team has made submissions to all ~N~ problems while the other team has only made submissions to the first ~K~ problems. At what time from the start of the contest will you win the contest for sure? You win the contest for sure at a given time if the other team cannot possibly achieve your team's score or higher, ignoring all future events.

However, your eyesight is worsening, and you can't see the scoreboard very well. During the contest, you will make ~Q~ corrections. For each correction, you notice that you were wrong about one of the existing submissions, so you correct your information about that submission. Each time, you want to know the new time in which your team is guaranteed to win. Corrections will persist.

Constraints

For all subtasks:

~1 \le N \le 10^5~

~0 \le K \le N~

~0 \le Q \le 2 \times 10^5~

~1 \le P,T,M \le 10^{10}~

Subtask 1 [20%]

~N = 4~

~P = 110~

~T = 180~

~M = 5~

~Q = 0~

Subtask 2 [20%]

~N \le 10^3~

~Q \le 2 \times 10^3~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line will contain ~N~, ~K~, ~Q~, ~P~, ~T~, and ~M~.

~N~ lines of input follow. The ~i^\text{th}~ line will contain ~p_{i1}~ ~(0 \le p_{i1} \le P)~ and ~t_{i1}~ ~(0 \le t_{i1} \le T)~, two non-negative integers specifying the number of points your team earned, and the submission time for the ~i^\text{th}~ problem.

~K~ lines of input follow. The ~j^\text{th}~ line will contain ~p_{j2}~ ~(0 \le p_{j2} \le P)~ and ~t_{j2}~ ~(0 \le t_{j2} \le T)~, two non-negative integers specifying the number of points the other team earned, and the submission time for the ~j^\text{th}~ problem.

~Q~ lines of input follow. Each line will contain four space separated integers in the form c n p t.

• ~c~ represents the submission team: ~1~ for your team or ~2~ for the other team.
• ~n~ is the problem number of the submission. If ~c = 1~, then ~1 \le n \le N~. If ~c = 2~, then ~1 \le n \le K~.
• ~p~ ~(0 \le p \le P)~ and ~t~ ~(0 \le t \le T)~ represent corrected points earned and submission time, respectively, of the given submission.

Output Specification

Output ~Q+1~ lines. Before the first correction and after each correction, output on a new line the earliest integer time in minutes from the start of the contest in which you are guaranteed to win. If this time is greater than ~T~ or if your team cannot win, print bamboozled.

Sample Input

4 3 2 110 180 5
110 20
85 96
90 49
38 112
110 60
60 24
51 89
1 2 42 53
2 1 33 44

Sample Output

150
bamboozled
112