Dangerous Discus

Given falling acid drops in columns, decide whether the single-pixel disc can stay at some height and cross without ever touching a drop.

Medium6Dynamic programmingSliding windowPrefix sumMathNo attempts yetTime limit2sMemory limit512 MB

Problem

You are playing a computer game in which you throw discs horizontally from the left side of the screen to the right. Acid keeps dripping straight down from several points in the ceiling to the ground, and any contact with the acid destroys your disc at once. After failing a few times, you want to know whether reaching the other side is possible at all.

There are nn dripping spots on row 0. A drop that starts at dripping spot kk falls vv pixels every time your disc moves one pixel to the right. When a drop reaches the ground, a new drop starts falling from the dripping spot in the same column, so each of those columns holds exactly one acid drop at every moment. At time tt, the drop in the column of dripping spot kk sits at vertical position

(yk+tv)modh,(y_k + t \cdot v) \bmod h,

where yky_k is the vertical position of the kk-th drop at time 0 and hh is the height of the ceiling.

Your disc and the acid drops move in alternation. First your disc moves one pixel to the right, then every acid drop moves vv pixels downwards, visiting each pixel on the way. Your disc is a single pixel thick and ww pixels wide, and an acid drop occupies a single pixel. The disc is destroyed if it ever occupies the same pixel as an acid drop. You can throw at any height between 0 and h1h - 1 inclusive, and the disc keeps that height for the whole journey. At time 0 the disc occupies columns w-w through 1-1 inclusive. The journey is complete once the left side of the disc reaches column 200000.

Input

The first line contains four integers nn, hh, vv and ww, where nn (1n2000001 \le n \le 200000) is the number of dripping spots, hh (1h2000001 \le h \le 200000) is the ceiling height, vv (1v5001 \le v \le 500) is the dripping speed and ww (1w5001 \le w \le 500) is the width of the disc.

Each of the next nn lines describes one acid drop with two integers xx (0x<2000000 \le x < 200000), the column of the drop, and yy (0y<h0 \le y < h), its vertical position at time 0.

No two acid drops have the same xx.

Output

Print VICTORY if some throwing height carries the disc through the acid without being destroyed. Otherwise print GAME OVER.