B - Pick Two Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

一直線状の倉庫があります。この倉庫に 偶数個 の荷物が保管されています。
倉庫の情報は文字列 S として与えらます。
倉庫は区画 1,2,\dots,|S| の |S| 個の区画からなり、 S の各文字は以下の情報を表します。

  • S の i 文字目が # であるとき、区画 i に荷物が 1 つ置かれている。
  • S の i 文字目が . であるとき、区画 i に荷物が置かれていない。

この倉庫にはロボットがあり、このロボットは以下の行動を倉庫から荷物が無くなるまで繰り返します。

  • 荷物をその荷物がある区画番号の小さい方から 2 つ回収する。回収された荷物は倉庫の外へ運び出される。

繰り返しの各回で運び出された 2 つの荷物が倉庫のどの区画にあったものかを求めてください。

制約

  • S は # と . からなる長さ 2 以上 1000 以下の文字列
  • 倉庫には偶数個の荷物が保管されている
  • 倉庫には 2 つ以上の荷物が保管されている

入力

入力は以下の形式で標準入力から与えられる。

S

出力

倉庫に保管されている荷物の総数を m とすると、 m/2 行出力せよ。
そのうち i 行目には、 i 回目の繰り返しで運び出された荷物が元々あった区画の番号を小さい方から順に カンマ区切り で出力せよ。

入力例 1

.#.##..##.#.###....#

出力例 1

2,4
5,8
9,11
13,14
15,20

区画 2,4,5,8,9,11,13,14,15,20 に荷物が保管されています。

  • 1 回目の繰り返しでは区画 2,4 にあった荷物が運び出されます。
  • 2 回目の繰り返しでは区画 5,8 にあった荷物が運び出されます。
  • 3 回目の繰り返しでは区画 9,11 にあった荷物が運び出されます。
  • 4 回目の繰り返しでは区画 13,14 にあった荷物が運び出されます。
  • 5 回目の繰り返しでは区画 15,20 にあった荷物が運び出されます。

Score : 200 points

Problem Statement

There is a linear warehouse, which stores an even number of packages.
The layout of the warehouse is represented by a string S.
The warehouse has |S| sections, numbered 1,2,\dots,|S|, and the string S describes them as follows:

  • When the i-th character of S is #, one package is placed in section i.
  • When the i-th character of S is ., no package is placed in section i.

The warehouse has a robot, which repeats the following action until there are no more packages in the warehouse:

  • Collect two packages from the sections with the smallest section numbers among the sections containing packages. The collected packages are carried out of the warehouse.

For each iteration, determine which sections of the warehouse the two packages that were carried out were originally located.

Constraints

  • S is a string consisting of # and . with length between 2 and 1000, inclusive.
  • The warehouse stores an even number of packages.
  • The warehouse stores at least two packages.

Input

The input is given from Standard Input in the following format:

S

Output

Let m be the total number of packages stored in the warehouse. Output m/2 lines.
The i-th line should contain the section numbers where the packages carried out in the i-th iteration were originally located, in ascending order, separated by a comma.

Sample Input 1

.#.##..##.#.###....#

Sample Output 1

2,4
5,8
9,11
13,14
15,20

Packages are stored in sections 2,4,5,8,9,11,13,14,15,20.

  • In the 1st iteration, packages from sections 2,4 are carried out.
  • In the 2nd iteration, packages from sections 5,8 are carried out.
  • In the 3rd iteration, packages from sections 9,11 are carried out.
  • In the 4th iteration, packages from sections 13,14 are carried out.
  • In the 5th iteration, packages from sections 15,20 are carried out.