Conveyor Belts

You work as an employee of the Boxing And Processing Company and must distribute boxes in one of the company's enormous warehouses. At BAPC Ltd., boxes travel on conveyor belts. Two belts can be merged into one by letting one drop its contents onto the other. A belt can also be split into two with a splitter, which sends a fixed portion of its input to its first output and the rest to its second output.

Adjustable splitters can divide their input in any ratio. To cut costs, your boss ordered cheap knock-off splitters that only divide their input in a fixed ratio $a : b$. You need $c : d$ splitters, but instead of arguing with the boss, you decide to build them yourself.

You must watch your costs. The system cannot have boxes that never leave it, and it cannot use splitters that never receive any boxes. You also cannot use too many $a : b$ splitters in total.

Given the ratios $a : b$ and $c : d$, construct a network of belts and at most 200 knock-off $a : b$ splitters. The network has a single global input belt and two global output belts, and the global input is distributed in the ratio $c : d$.

A splitter with ratio $x : y$ sends exactly $\frac{x}{x+y}$ of its incoming boxes to the first output and exactly $\frac{y}{x+y}$ to the second output.

The first line contains two integers $a$ and $b$ with $1 \le a, b \le 10^9$ and $a + b \le 10^9$, the ratio of the knock-off splitter.

The second line contains two integers $c$ and $d$ with $1 \le c, d \le 10^9$ and $c + d \le 10^9$, the desired ratio.

The first line contains an integer $n$ with $1 \le n \le 200$, the number of $a : b$ splitters used.

Then follow $n$ lines. The $i$-th line contains two integers $l_i$ and $r_i$ with $-2 \le l_i, r_i < n$. Here $l_i$ is the splitter connected to the left output of the $i$-th splitter, which receives $\frac{a}{a+b}$ of its input. Similarly, $r_i$ is the splitter receiving $\frac{b}{a+b}$ of its input. Splitters are indexed from 0. The global input is connected to splitter 0. The values $-1$ and $-2$ stand for the first and second global output, which must receive $\frac{c}{c+d}$ and $\frac{d}{c+d}$ of the global input.

A splitter cannot be placed where no box reaches it, and it cannot be placed where a box passing through it never reaches an output. If several solutions exist, any one is accepted.