0230 - シャッフル2012 (Shuffle2012)

時間制限 8 秒 / メモリ制限 256 MB / 得点 5 / Writer root / x 0 / 統計 /

TLE
8sec
MLE
256MB
得点
5

問題

JOI君は, 1 から N までの数が, 1 枚に 1 つ書かれている N 枚のカードをシャッフルして遊んでいる. ここで, N は偶数である.

JOI君は、次の 3 種類のいずれかの方法でシャッフルする :

  1. 1 枚目から N / 2 枚目までのカード列をそれぞれ A1, A2, … , AN/2, N / 2 + 1 枚目から N 枚目までのカード列を B1, B2, …, BN/2 とする.
    このとき, 新しいカード列を B1, A1, B2, A2, …, BN/2, AN/2 とする. これをシャッフル 1 とする.
  2. 今あるカード列を逆順にする. すなわち, 今までのカード列を A1, A2, …, AN とすると, これを AN, AN-1, …, A2, A1 とする. これをシャッフル 2 とする.
  3. ある整数 K (1 ≦ K ＜ N)について, 1 枚目から K 枚目までのカードを A1, A2, …, AK とし, K + 1 枚目から N 枚目までのカードを B1, B2, …, BN - K とする.
    このとき, 新しいカード列を B1, B2, …, BN-K, A1, A2, …, AK とする. これをシャッフル 3 とする.

JOI君は, 最初に 1 から昇順にカード列を並べ, M 個のシャッフルを 1 セットとして繰り返す. このとき, JOI君はこのカード列を何セット分シャッフルすると昇順に戻るか気になった.

入力として N, M と M 個からなるシャッフルのセット Ci の情報が与えられるとき, JOI君が元のカード列を得るために, 繰り返さないといけないセットの最小回数を出力せよ.

入力

入力は M + 1 行からなる.
1 行目には 2 つの整数 N, M ( 1 ≦ N ≦ 10000, 1 ≦ M ≦ 1000 ) が空白を区切りとして書かれている. N は偶数である.
1 + i 行目には, 整数 Ci ( 1 ≦ Ci ≦ 3 ) が書かれている.
整数 Ci が 1 か 2 であるとき, これはそれぞれシャッフル 1 またはシャッフル 2 を表す.
整数 Ci が 3 であるとき, 空白区切りで整数 Ki が書かれる. これは, 数 Ki でシャッフル 3 を行うことを表す.

出力

1 行に, JOI君が元のカード列を得るために, 繰り返さないと行けないセットの最小回数を出力せよ.
ここで, シャッフルを続ければ必ず元のカード列に戻ることが保証されている.
また, 入力の 40 %分では, 答えが 231 - 1 を超えない. また, すべての入力について, 答えは 263 - 1 を超えない.

入出力例

入力例 1

4 2
1
3 2

出力例 1

2

入出力例 1 では, 次のように 2 回のセットで元のカード列に戻る.

(0) 1 2 3 4 [初期状態]
(1) 3 1 4 2 [シャッフル 1]
    4 2 3 1 [K = 2でシャッフル 3]
(2) 3 4 1 2 [シャッフル 1]
    1 2 3 4 [K = 2でシャッフル 3]

入力例 2

10 3
2
2
3 8

出力例 2

5

入出力例 2 では, 次のように 5 回のセットで元のカード列に戻る. セット 1 の途中で元の並びに戻っているが, ちょうどセットが終わるときに元に戻っていなければならないことに注意せよ. 

(0) 1 2 3 4 5 6 7 8 9 10 [初期状態]
(1) 10 9 8 7 6 5 4 3 2 1 [シャッフル 2]
    1 2 3 4 5 6 7 8 9 10 [シャッフル 2]
    9 10 1 2 3 4 5 6 7 8 [K = 8でシャッフル 3]
(2) 8 7 6 5 4 3 2 1 10 9 [シャッフル 2]
    9 10 1 2 3 4 5 6 7 8 [シャッフル 2]
    7 8 9 10 1 2 3 4 5 6 [K = 8でシャッフル 3]
(3) 6 5 4 3 2 1 10 9 8 7 [シャッフル 2]
    7 8 9 10 1 2 3 4 5 6 [シャッフル 2]
    5 6 7 8 9 10 1 2 3 4 [K = 8でシャッフル 3]
(4) 4 3 2 1 10 9 8 7 6 5 [シャッフル 2]
    5 6 7 8 9 10 1 2 3 4 [シャッフル 2]
    3 4 5 6 7 8 9 10 1 2 [K = 8でシャッフル 3]
(5) 2 1 10 9 8 7 6 5 4 3 [シャッフル 2]
    3 4 5 6 7 8 9 10 1 2 [シャッフル 2]
    1 2 3 4 5 6 7 8 9 10 [K = 8でシャッフル 3]