This page is still under construction.

Parts of this page are still being built. What you see may change.

Game

Time limit2sMemory limit512 MB

Summary
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, nn columns of different heights stand in a row. The boys have mm 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 l1l_1 and at most r1r_1. 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 l2l_2 and at most r2r_2, 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 nn and mm, the number of columns and the number of rings, respectively (1≤m≤n≤1051 \le m \le n \le 10^5).

The next two lines contain the numbers l1l_1, r1r_1 and l2l_2, r2r_2, the minimum and maximum heights of the columns onto which Petya and Vasya can throw rings, respectively (1≤l1,r1,l2,r2≤1091 \le l_1, r_1, l_2, r_2 \le 10^9).

The last line contains nn numbers describing the heights of the columns. The height of each column is a positive integer and does not exceed 10910^9.

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.

Examples3

  1. Example 1

    Input
    4 3
    1 2
    2 4
    1 2 3 4
    
    Expected output
    Petya
    
  2. Example 2

    Input
    4 4
    1 4
    1 4
    1 2 3 4
    
    Expected output
    Draw
    
  3. Example 3

    Input
    4 4
    1 2
    1 4
    1 2 3 4
    
    Expected output
    Vasya