시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB106363353.226%

문제

이번 겨울 캠프에서 N(1 ≤ N ≤ 1,000,000)명의 학생들이 무더기로 인터넷을 하다 걸렸다. 이에 격분한 김조교는 학생들을 일렬로 세우고, 다음과 같은 벌칙을 실시하도록 하였다.

  1. 먼저 처음의 상태는 학생들이 임의로 정할 수 있다. 학생들은 앉아 있을 수도 있으며, 일어나 있을 수도 있다. 이때의 상태를 임의로 0번째 단계라고 하자.
  2. 이 벌칙에는 단계가 있는데, 다음 단계로 넘어갈 때에는 자신의 오른쪽 학생의 상태에 따라 자신의 상태를 결정해야 한다. 만일 이번 단계에 오른쪽 학생이 일어서 있으면 자신은 다음 턴에 상태를 바꾸어야 한다. 즉 일어나 있었으면 앉아야 하고, 앉아 있었으면 일어나야 한다. 만일 이번 턴에 오른쪽 학생이 앉아 있으면 자신은 다음 턴에 상태를 바꿀 필요 없이 그대로 있어도 된다. (바꾸면 안 된다)
  3. 학생의 번호는 편의상 왼쪽부터 오른쪽으로 1부터 N까지 매겨진다. T LOGIN을 제공하여 학생들이 인터넷을 할 수 있도록 해 준 N번 학생은 특별히 가장 어려운데, 자신의 오른쪽 학생이 없지만 1번 학생을 자신의 오른쪽 학생으로 생각하고 벌칙을 받아야 한다.

예를 들어 N=4이고, 처음에 4번 학생만 일어나 있다고 하자. 이 벌칙이 몇 번 진행된 상태는 다음과 같다. 약삭빠른 학생들은 어이없게도 순식간에 머리를 굴려서, 4단계 이후 모두가 쉴 수 있는 다음과 같은 초기 상태를 정하고야 말았다.

  학생 1 학생 2 학생 3 학생 4
0단계 앉음 앉음 앉음 일어남
1단계 앉음 앉음 일어남 일어남
2단계 앉음 일어남 앉음 일어남
3단계 일어남 일어남 일어남 일어남
4단계 앉음 앉음 앉음 앉음
허걱...

학생들이 뉘우치지는 않고 어떡하면 벌칙을 덜 받을 수 있을까만을 궁리하는 모습에 격분한 김조교는 학생들에게 이 벌칙을 무려 M(1 ≤ M ≤ 1,000,000,000)단계까지 반복하도록 하고, 휭 나가버렸다. 김 조교는 곧 돌아올텐데, M번째 단계에 학생들은 어떤 모습을 하고 있어야 할까?

입력

첫째 줄에 N과 M이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 학생들의 0단계 상태가 빈 칸 없이 N개의 문자열로 주어진다. 1번 학생부터 N번 학생까지의 상태를 순서대로 나타낸 것으로, u는 일어난 상태, d는 앉은 상태를 나타낸다.

출력

첫째 줄에 M번째 단계에 학생들의 상태를 입력과 마찬가지 형식으로 출력한다.

예제 입력 1

4 1000000000
dddu

예제 출력 1

dddd