원정

flickr.com에서 가져온 이미지

어린 Óli는 원정을 떠나려 한다. 가는 길에 그는 세 가지 종류의 물건, 즉 돈, 금, 보석을 마주치게 된다. 물건을 마주치면 원할 경우 그 물건을 자신의 배낭 맨 위에 넣을 수 있다. 하지만 Óli는 가는 길에 악당들도 마주치게 된다. 악당은 세 종류이며, 이들은 모두 Óli에게 서로 다른 종류의 물건을 요구한다. 사악한 은행가는 돈을 원하고, 사악한 금광 채굴자는 금을 원하며, 사악한 보석상은 보석을 원한다.

어린 Óli는 이 악당들의 요구를 따를 수밖에 없으며, 각 악당에게 그들이 요구하는 종류의 물건을 하나 주어야 한다. 하지만 Óli의 배낭은 다소 비좁아서, Óli는 가방의 맨 위에 있는 물건(즉, 가방에 가장 마지막으로 넣은 물건)에만 손이 닿는다. Óli에게 필요한 물건이 가방의 더 아래쪽에 있다면, 가방 맨 위에 있는 물건들을 버릴 수 있지만, 그 물건들은 가방에서 꺼내는 순간 사라지며 다시 가방에 들어가지 않는다. Óli가 악당이 요구하는 물건을 가지고 있지 않다면, Óli는 원정을 끝마칠 수 없다.

Óli가 원정을 끝마칠 수 있는지 확인하도록 도와주고, 가능하다면 원정이 끝났을 때 Óli가 가질 수 있는 돈, 금, 보석의 최대량이 얼마인지 구하라.

채점

그룹 | 점수 | 제한

1 | 25 | 원정에 악당이 없다

2 | 35 | 원정은 최대 20개의 칸으로 이루어진다

3 | 40 | 추가 제한 없음

입력은 어린 Óli의 원정을 나타내는 한 줄로 이루어지며, 다음 문자들로 구성된다.

• ``p`'는 땅에 있는 돈을 나타낸다.

• ``g`'는 땅에 있는 금을 나타낸다.

• ``o`'는 땅에 있는 보석을 나타낸다.

• ``P`'는 사악한 은행가를 나타낸다.

• ``G`'는 사악한 금광 채굴자를 나타낸다.

• ``O`'는 사악한 보석상을 나타낸다.

• ``.`'는 땅을 나타낸다.

Óli는 가장 왼쪽 칸에서 시작해 항상 오른쪽으로 걸어간다. (Óli가 물건을 두고 간다면, 나중에 그것을 가지러 돌아올 수 없다.) Óli가 가장 오른쪽 칸에 도착하면 원정이 끝난다.

원정은 최대 $10^6$개의 칸으로 이루어진다.

Óli가 원정의 끝에 도달할 수 없다면, Neibb을 포함하는 한 줄을 출력한다. 그렇지 않으면 Óli가 원정을 마친 뒤 가질 수 있는 돈, 금, 보석의 최대량을 나타내는 세 수를 각각 한 줄에 하나씩 출력한다.