Have you ever met the members of the ten European royal houses, the Argentinian football team including their coach Diego Maradona, or all of the Turing and Fields medal prize winners? We have invited many celebrities from all over the world to the CEOI 2010 closing ceremony. Unfortunately, very few of them responded to our invitation, and those who did, politely rejected. Nevertheless, do not forget to bring your camera to the ceremony, one never knows who might turn up! As you can imagine, the security of the guests is of utmost importance. The problem is how to seat their bodyguards in the audience so that maximal security is guaranteed. The auditorium contains many seats, arranged into a large grid. Based on the safety regulations a security expert has determined necessary bodyguard counts for each row and each column of the auditorium. You are given the required number of bodyguards for each row and column of the auditorium. This information is given in a compressed form as explained below. Determine whether it is possible to place the bodyguards in such a way that in each row and each column we would have exactly the required number of bodyguards. Assume that the auditorium is initially empty, i.e., you may seat bodyguards wherever you wish. Each seat may only be occupied by a single bodyguard. \InputFile The input begins with the description of the rows. The first line of the input contains one positive integer \textbf{R}: the number of groups of rows. \textbf{R} lines follow. Each of these lines contains \textbf{2} positive integers: the required number of bodyguards in each row of the group and the number of rows that form the group. This is followed by the description of column groups. The next line contains one positive integer \textbf{C}: the number of groups of columns. \textbf{C} lines follow. Each of these lines contains \textbf{2} positive integers: the required number of bodyguards in each column of the group and the number of columns that form the group. \textbf{Constraints} You may assume that the total number of bodyguards required by row constrains is the same as the total number of bodyguards required by column constraints. You may assume that this total number of bodyguards is at most \textbf{10^18}. You may assume that all numbers are positive integers that do not exceed \textbf{1000000000}. You may assume that \textbf{1} ≤ \textbf{R}, \textbf{C} ≤ \textbf{200000}. Several batches of test cases, worth a total of \textbf{50} points, satisfy the following criteria: \begin{itemize} \item the total number of rows in the auditorium will be at most \textbf{2000} \item the total number of columns in the auditorium will be at most \textbf{2000} \item the total number of bodyguards will be at most \textbf{1000000}. \end{itemize} In a test batch worth another \textbf{10} points we have \textbf{R}, \textbf{C} ≤ \textbf{100} in each test case. \OutputFile Output a single line with the number "\textbf{1}" if the constraints are satisfiable and the number "\textbf{0}" otherwise (quotes for clarity).