머릿결 전쟁

블롭들은 늘 새로움을 추구해 왔다. 이번에도 블롭들은 새로운 느낌을 원했고, 그래서 매일 하늘에 기도하게 되었다.

이 기도를 들은 토카는 블롭들에게 양갈래 머리를 내려주었고, 블롭들은 대양갈래 시대를 맞이한다.

양갈래 블롭

그러나 일부 블롭들은 여기서 더 새로운 헤어 스타일을 원했고, 머리를 묶어 포니테일 블롭이 되었다.

포니테일 블롭의 등장에 슬퍼하는 양갈래 블롭들

처음에는 이상한 블롭 취급을 하며 넘길 수 있는 수준이었다. 하지만 포니테일 블롭의 수가 하나둘씩 늘어나 어느덧 양갈래 블롭들과 비슷한 수가 되었다.

양갈래 블롭들과 포니테일 블롭들은 서로를 싫어하는 감정이 격해져, 결국 '머릿결 전쟁'이 터지고 말았다!

블롭들은 평화를 좋아했기 때문에, 피를 보는 전쟁 대신 서로 기량을 겨루는 전쟁을 치르기로 합의했다. 토카는 경기 장소로 '양갈래 굴'을 골랐다. 양갈래 굴은 한때 블롭들의 주요 채광지였다. 광산업이 활발하던 당시에는 입구에서 깊이 $D$까지 총 $2^D-1$개의 방으로 이루어진 완전 이진 트리 형태였고, $i$번 방과 $\left \lfloor \frac{i}{2} \right \rfloor$번 방($2 \le i \le 2^D-1$)을 잇는 길목이 있었다.

그러나 광산업이 쇠퇴하면서 양갈래 굴은 오랫동안 쓰이지 않았고, 길목 $N$군데가 파손되어 탐색을 위해 지나다닐 수 없게 되었다.

그래도 전쟁은 치러져야 했기 때문에, 갈 수 없는 방을 제외한 모든 방을 가장 빠르게 탐색하는 세력이 이기는 것으로 정했다.

블롭들은 기본적으로 한 방에서 인접한 다른 방까지 가는 데 $U$의 시간이 걸린다. 양갈래 블롭들과 포니테일 블롭들은 서로 다른 탐색 방법을 택했다.

양갈래 블롭들은 분기점에 놓일 때마다 세력을 반으로 나누어 탐색한다. 나눌 때 블롭이 충분히 많으면 세력은 언제든지 나눌 수 있다. 다만 한 번 나눌 때마다 나뉜 세력이 인접한 방까지 가는 시간이 $T$만큼 늘어난다.

양갈래 블롭들은 동시다발적으로 탐색하므로, 가장 오래 걸린 팀의 총 탐색 시간을 양갈래 블롭들의 탐색 시간으로 본다.

포니테일 블롭들은 다 같이 한 곳으로 빠르게 탐색한다. 분기점이 나오면 왼쪽을 우선해서 탐색한다. 더 이상 탐색할 방이 없으면 위로 돌아간다. 이때도 탐색 시간이 $U$만큼 소모됨에 유의한다.

각 블롭은 길목을 탐색할 때마다 그 탐색 시간만큼만 시간이 흐르고, 그 외의 시간은 무시한다. 모든 방을 탐색하는 즉시 탐색이 끝난다.

아래 그림은 왼쪽이 양갈래 블롭들의 탐색 방법, 오른쪽이 포니테일 블롭들의 탐색 방법이다.

그렇게 전쟁이 선포되고 탐색이 시작되었다! 이 전쟁에서 어느 세력이 승리할지 구해보자.

첫째 줄에 양갈래 굴의 가장 깊은 방의 깊이 $D(1 \le D \le 12)$, 파손된 길목의 수 $N(0 \le N \le 2^D-2)$, 각 블롭 세력이 기본적으로 탐색하는 시간 $U(1 \le U \le 100)$, 양갈래 블롭들이 갈라졌을 때 추가로 걸리는 시간 $T(U < T \le 150)$가 공백으로 구분되어 주어진다.

$D$, $N$, $U$, $T$는 모두 정수이다.

둘째 줄부터 $N$개의 줄에 걸쳐 파손된 길목의 시작점과 끝점 $s, e(1 \le s < e \le 2^D-1)$가 공백으로 구분되어 주어진다. 같은 길목이 두 번 이상 등장하지 않는다.

양갈래 블롭의 탐색이 더 빠르면 :blob_twintail_aww:를 출력한다. 포니테일 블롭의 탐색이 더 빠르면 :blob_twintail_sad:를 출력한다.

두 블롭이 동시에 탐색을 마치면 :blob_twintail_thinking:을 출력한다.