아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

게임

시간 제한2초메모리 제한512 MB

요약
두 사람이 번갈아 자신이 던질 수 있는 기둥을 차지하며, 더 많은 기둥을 가져가는 쪽이 이기는 최적 플레이의 승자를 판정한다.
난이도

보통10점 중 6점

유형
그리디, 게임 이론, 정렬, 구간
정답자
아직 제출이 없습니다

문제

체육 시간에 1학년 페탸와 바샤가 재미있는 게임을 한다. 두 아이 앞에 높이가 서로 다른 nn개의 기둥이 일렬로 서 있다. 두 아이에게는 mm개의 고리가 있고, 번갈아 가며 기둥에 고리를 던진다. 이미 고리가 있는 기둥에는 고리를 던질 수 없다. 페탸가 먼저 던진다.

페탸는 높이가 l1l_1 이상 r1r_1 이하인 기둥에만 고리를 던질 수 있다. 너무 높거나 너무 낮은 기둥에는 고리를 던질 수 없다. 높이가 조건에 맞는 기둥이라면 던진 고리는 반드시 성공한다. 마찬가지로 바샤는 높이가 l2l_2 이상 r2r_2 이하인 기둥에만 고리를 던질 수 있고, 그러한 기둥이라면 어디에든 반드시 성공한다.

체육 교사 안드레이 세르게예비치는 게임이 끝난 뒤 기둥에 고리를 더 많이 던진 아이에게 5점을 주겠다고 약속했다. 두 아이가 최적으로 플레이할 때 누가 이기는지 구하시오.

입력

첫째 줄에 기둥의 수 nn과 고리의 수 mm이 주어진다 (1≤m≤n≤1051 \le m \le n \le 10^5).

다음 두 줄에 페탸와 바샤가 고리를 던질 수 있는 기둥 높이의 최솟값과 최댓값 l1l_1, r1r_1과 l2l_2, r2r_2가 각각 주어진다 (1≤l1,r1,l2,r2≤1091 \le l_1, r_1, l_2, r_2 \le 10^9).

마지막 줄에 기둥의 높이를 나타내는 nn개의 수가 주어진다. 각 기둥의 높이는 양의 정수이고 10910^9를 넘지 않는다.

출력

페탸가 이기면 Petya, 바샤가 이기면 Vasya, 두 아이가 최적으로 플레이했을 때 기둥에 던진 고리의 수가 같으면 Draw를 출력한다.

힌트

첫 번째 예에서 페탸는 먼저 높이 2인 기둥에 고리를 던진다. 바샤는 높이 3 또는 4인 기둥에 고리를 던져 응수할 수 있지만, 어느 쪽을 고르든 페탸가 높이 1인 기둥에 세 번째 고리를 던져 이긴다. 페탸는 고리 2개를 던졌고 바샤는 1개만 던졌다.

두 번째 예에서는 두 선수 모두 아무 기둥에나 고리를 던질 수 있으므로 둘 다 고리 2개씩 던져 무승부로 끝난다.

세 번째 예에서 페탸는 첫 번째 차례에 자신이 던질 수 있는 두 기둥 중 하나에 고리를 던지고, 바샤는 두 번째 차례에 그중 나머지 기둥에 고리를 던진다. 이제 페탸에게는 고리를 던질 수 있는 기둥이 없어 세 번째 고리를 던지지만 빗나간다. 바샤는 마지막 고리를 높이 3 또는 4인 기둥 아무 곳에나 던진다.

예제3

  1. 예제 1

    입력
    4 3
    1 2
    2 4
    1 2 3 4
    
    예상 출력
    Petya
    
  2. 예제 2

    입력
    4 4
    1 4
    1 4
    1 2 3 4
    
    예상 출력
    Draw
    
  3. 예제 3

    입력
    4 4
    1 2
    1 4
    1 2 3 4
    
    예상 출력
    Vasya