After long-term research and lots of experiments leading Megapolian automobile manufacturer «AutoVoz» released a brand new car model named «Lada Malina». One of the most impressive features of «Lada Malina» is its highly efficient environment-friendly engines. Consider car as a point in Oxy plane. Car is equipped with k engines numbered from 1 to k . Each engine is defined by its velocity vector whose coordinates are ( vx i , vy i ) measured in distance units per day. An engine may be turned on at any level w i , that is a real number between - 1 and + 1 (inclusive) that result in a term of ( w i · vx i , w i · vy i ) in the final car velocity. Namely, the final car velocity is equal to Formally, if car moves with constant values of w i during the whole day then its x -coordinate will change by the first component of an expression above, and its y -coordinate will change by the second component of an expression above. For example, if all w i are equal to zero, the car won't move, and if all w i are equal to zero except w 1 = 1 , then car will move with the velocity of the first engine. There are n factories in Megapolia, i -th of them is located in ( fx i , fy i ) . On the i -th factory there are a i cars «Lada Malina» that are ready for operation. As an attempt to increase sales of a new car, «AutoVoz» is going to hold an international exposition of cars. There are q options of exposition location and time, in the i -th of them exposition will happen in a point with coordinates ( px i , py i ) in t i days. Of course, at the «AutoVoz» is going to bring as much new cars from factories as possible to the place of exposition. Cars are going to be moved by enabling their engines on some certain levels, such that at the beginning of an exposition car gets exactly to the exposition location. However, for some of the options it may be impossible to bring cars from some of the factories to the exposition location by the moment of an exposition. Your task is to det