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

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

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.*