Game
Time limit2sMemory limit512 MB
Two players alternately claim columns they can reach; each wants to claim more columns than the other, and the winner under optimal play is reported.
- Level
Medium6 of 10
- Topics
- Greedy, Game theory, Sorting, Intervals
- Solved
- No attempts yet
Problem
In physical education class, first-graders Petya and Vasya play an exciting game. In front of the children, columns of different heights stand in a row. The boys have rings, which they throw onto the columns in turn, and a ring cannot be thrown onto a column that already has a ring. Petya throws first.
The boys found out that Petya can throw a ring onto a column only if the height of that column is at least and at most . He cannot throw a ring onto a column that is too tall or too short. But if a column has a suitable height, the throw is guaranteed to succeed. Similarly, Vasya can throw a ring only onto columns with height at least and at most , and he is guaranteed to hit any such column.
The gym teacher Andrei Sergeevich promised to give a top grade to whichever boy throws more rings onto the columns over the course of the game. Help the boys determine who wins under optimal play.
Input
The first line of the input file contains two integers and , the number of columns and the number of rings, respectively ().
The next two lines contain the numbers , and , , the minimum and maximum heights of the columns onto which Petya and Vasya can throw rings, respectively ().
The last line contains numbers describing the heights of the columns. The height of each column is a positive integer and does not exceed .
Output
Output Petya if Petya wins, Vasya if Vasya wins, or Draw if, under optimal play, both boys throw the same number of rings onto the columns.
Hint
In the first example, Petya first throws a ring onto the column of height 2. Vasya can respond by throwing a ring onto a column of height 3 or 4, but whichever he chooses, Petya throws his third ring onto the column of height 1 and wins: he threw 2 rings, and Vasya only one.
In the second example, each player can throw a ring onto any column, so both throw two rings each and the game ends in a draw.
In the third example, Petya on his first move throws a ring onto one of the two columns available to him, and Vasya on his second move throws a ring onto the other of those columns. Now Petya has no column onto which he can throw a ring; he throws his third ring but misses. Vasya throws his last ring onto any of the columns of height 3 or 4.