시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 239 30 27 54.000%

문제

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 순례자는 위치한 성지에서 다른 성지로 이동하고, 성지에 도착할 때마다 신께 기도를 드린다.

지상에는 총 $N$ 개의 성지가 있어 $1$에서 $N$사이의 번호가 붙어있고, $i$번 성지에는 성직자가 $i$명 있다. 순례자는 적당한 순서를 정해서, 모든 성지를 정확히 한 번씩 방문해서 시작했던 성지로 돌아오는 순례 계획을 세우고 있다.

순례자가 $i$번 성지에서 $j$번 성지로 이동할 때, $i$번 성지에 있는 성직자와 $j$번 성지에 있는 성직자 총 $i+j$ 명이 순례자와 순례의 안녕을 기원하는 정신적인 의식을 거행한다. 순례자는 $N$번 이동하기 때문에 의식은 총 $N$번 열리는데, 각각의 의식에 몇 명이 모였는지에 따라 의식은 질서의 성질 혹은 혼돈의 성질을 갖게 된다.

성직자 $x$명의 정신을 일렬로 세우지 않고 직사각형 모양으로 배치 할 수 있다면, $x$를 질서의 수라고 한다. 즉, $x = pq$인 1보다 큰 자연수 $p$와 $q$가 존재하면 $x$를 질서의 수라고 한다. 그리고 질서의 수가 아닌 자연수들은 혼돈의 수이다. 질서의 수의 예로는 $420$, $123$ 등이 있고 혼돈의 수의 예로는 $2$, $3$, $7$, $1\ 000\ 000\ 007$ 등이 있다.

어떤 의식에 모인 사람의 수가 질서의 수가 되면, 그 의식은 질서의 의식이 된다. 그것이 아니라면 사람의 수가 혼돈의 수가 되기 때문에, 그 의식은 혼돈의 의식이 된다.

질서의 순례자는 순례하는 과정에서 질서의 의식이 최대한 많았으면 좋겠다고 생각하고, 혼돈의 순례자는 순례하는 과정에서 혼돈의 의식이 최대한 많았으면 좋겠다고 생각한다. 각 순례자를 위해서 어떤 순서로 성지를 순례해야 하는지 구하여라.

입력

첫 번째 줄에, 문자열 $S$와 성지의 개수를 나타내는 자연수 $N$이 공백으로 구분되어 주어진다. $S$는 order혹은 chaos이다. $S$가 order인 경우에는 질서의 순례자가 순례하고, chaos인 경우에는 혼돈의 순례자가 순례한다는 것을 의미한다.

출력

첫 번째 줄에, 순례자가 성지를 방문하는 순서를 의미하는 $N$ 개의 수를 공백으로 구분하여 출력하라. 가능한 방문 순서가 여럿 있을 경우 그중 아무거나 하나를 출력해도 좋다.

서브태스크 1 (1점)

  • $2 \le N \le 8$

서브태스크 2 (10점)

  • $S = $order
  • $2 \le N \le 888\ 888$

서브태스크 3 (100점)

  • $S = $chaos
  • $2 \le N \le 888\ 888$

예제 입력 1

chaos 4

예제 출력 1

1 2 3 4

예제 입력 2

order 9

예제 출력 2

6 3 9 1 5 4 2 7 8

출처

Contest > 전시관 > 제1 전시관 7번

  • 데이터를 추가한 사람: doju
  • 문제를 만든 사람: ho94949

채점

  • 예제는 채점하지 않는다.