In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

Snobbish citizens of Byteotia enjoy playing the laser pool. The pool table has a shape of a rectangle. The rails of the table are wide and contain pairs of laser transmitters. When all the transmitters are on, the table is covered by "horizontal" and "vertical" laser beams so that the -th horizontal beam (for ) crosses the -th vertical beam (for ) in the point . The transmitters can be turned on or off independently.

Laser pool is played with a ball of diameter . When the ball crosses at least one of the laser beams, a hit signal is displayed.

Initially the ball is located at the point . The ball was hit with a cue so that its initial velocity vector is and it rolled without friction for units of time. The collisions of the ball with the cushion were perfectly elastic. How many times was the hit signal displayed (possibly taking into account the initial moment of the ball's movement)?

The first line of the standard input contains two integers
and () that represent the dimensions of the table.
The second line contains an -character word composed of the digits `0` i `1`.
The -th letter of the word describes the state of the -th horizontal transmitter
where `0` means that the transmitter is off and `1` means that it is on.
The third line contains an -character word that describes the state of the vertical transmitters.

The fourth line of the input contains an integer (): the number of queries. Each of the following lines contains five integers , , , , (, , , ) that describe the initial position, the velocity of the ball and the duration of its movement.

Your program should output exactly lines to the standard output: the answers to the respective queries. Each answer should have the form of a single integer: the number of times the hit signal was displayed.

For the input data:

4 6 1010 010110 1 5 2 1 1 8

the correct result is:

6

*Task author: Tomasz Idziaszek.*