Bear Roars
Tag(s):

## Geometry, Math, Medium-Hard

Problem
Editorial
Analytics

Let's say we live on the infinite plane. You own a quadratic field, with bottom-left corner and top-right corner at points $(0, 0)$ and $(a,a)$ respectively. From time to time, your field is destroyed by animals, what doesn't make you very happy.

Limak is a big and dreadful grizzly bear. He lives at the point $(bx, by)$.

Other animals live in herds. A herd is a group of animals described by five integers $k, x0, y0, dx, dy$. There are k animals in a herd, numbered 0 through $k-1$ for convenience. An animal i lives at the point $(x0 + i \cdot dx, y0 + i \cdot dy)$.

Each of $k + 1$ animals (bear Limak and k animals from a herd) lives strictly outside your field. Also, none two of those animals live at the same point.

When bear Limak roars, all other animals get scared and run away from him. After hearing the roar from some direction, an animal runs in the opposite direction. An example is showed in the Explanation section below.

You are given T independent test cases, each describing one herd. For each test case, count how many animals from a herd will run through your field after hearing Limak. Animals which only touch the border must be counted too.

### Input format

The first line contains four integers $T, a, bx, by$ — the number of herds, the size of your field and coordinates of bear Limak, respectively.

Each of the next T lines contains five integers $k, x0, y0, dx, dy$, describing one herd.

### Output format

For each test case print one integer in a separate line — the number of animals that will at least touch your field, while running away from Limak.

### Constraints

• $1 \le T \le 5000$
• $1 \le a \le 10^9$
• $-10^9 \le bx, by, x0, y0, dx, dy \le 10^9$
• $2 \le k \le 10^9$
• None two animals from one herd live at the same point.
• No other animal coincides with bear Limak.
• All animals live strictly outside your field. In other words, $x < 0$ or $x > a$ or $y < 0$ or $y > a$, where $x, y$ are coordinates of any animal (including Limak).
SAMPLE INPUT
1 5 15 15
3 0 16 8 -8
SAMPLE OUTPUT
1
Explanation

Limak is at the point H, and other animals at E,F,G. A field is a square ABCD. You can see in which direction each animal is going to run - among them only F will cross the field.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup - First Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Bit Manipulation
• Math > Number Theory
• Algorithms > String Algorithms
• Math > Counting