def main_ring(ball)                #ball:球の個数
  #使用する変数を用意
  @ball = ball                     #関数を分けているのでインスタンス変数化
  @mball = @ball - 1               #ループ内の計算を減らすために用意
  @sum = @ball * @mball + 1        #各球の数の総和
  @a = []                          #ネックレス　球の数の並びを格納した配列
  @ans = []                        #答えの配列
  @ansnum = 0                      #答えの個数
  skip = @ball / 2                 #対称性を考慮したスキップ処理に使用
  mskip = skip - 1
  @path = [1,2,4]                  #n番目に入れる数の配列
  
  #@a = [1,2,0,0……]から始める
  @p_sum = [[1],[2,3]]             #n番目に入れた数を含む和の配列
  @num = 2                         #入れた球の数
  @route = [[]]                    #球の位置の候補
  for i in 1..@mball
    @route[i] = []
    @a[i] = 0
  end
  @a[0] = 1
  @a[1] = 2
  x = 0
  for i in 1..mskip                #@a[skip]=2は後回し
    @route[1][x] = i               #対称性から2の位置を制限
    x += 1
  end
  
  
  #例外処理(ball=1,2)
  return [[1]] if ball == 1
  return [[2,1]] if ball == 2
  
  
  ringing                          #2が1~mskip番目にある時の解を探す
  
  
  #@a[skip]=2に設定
  if @ball % 2 == 0
    if ball == 4
      @p_sum = [[1],[2],[3,4,5,6]]
      @path = [1,2,3,7]
    else
      @p_sum = [[1],[2],[3,4]]
      @path = [1,2,3,5]
    end
    @num = 3
    x = 0
    for i in 1..mskip              #ballが偶数なら対称性から3の位置を制限
      @route[2][x] = i
      x += 1
    end
    @a[skip] = 2
    @a[1] = 3
  else
    @p_sum = [[1],[2]]
    @path = [1,2,3]
    @num = 2
    @a[skip] = 2
  end
  
  ringing                          #2がskip番目にある時の解を探す
  
  
  return @ans                      #答えを返す
end



def listing(s)                     #s:入れた数の場所　@p_sum作成処理
  @p_sum[@num]  = [@a[s]]
  listnum = 1                      #和の個数
  
  for i in 1...@mball              #右回りの和を計算
    t = (s + i) % @ball            #i:足す球の個数
    break if @a[t] == 0
    x = @a[s]
    for j in 1..i                  #j:足す球の位置
      j += s
      j %= @ball
      x += @a[j]
    end
    if inc?(x)                     #xが@p_sumに含まれていれば次の候補へ
      moving
      return
    end
    @p_sum[@num][listnum] = x
    listnum += 1
  end
  
  z = listnum                      #右回りの和の個数
  for i in 1...@mball              #左回りの和を計算
    break if @a[s - i] == 0        #i:足す球の個数
    x = @a[s]
    for j in 1..i                  #j:足す球の位置
      k = s - j
      x += @a[k]
    end
    if inc?(x)                     #xが@p_sumに含まれていれば次の候補へ
      moving
      return
    end
    @p_sum[@num][listnum] = x
    listnum += 1
                                   #sを挟む和を計算
    g = x - @a[s]                  #左回りの腕の部分だけの和
    for e in 1...z                 #e:右回りの和の位置
      break if i + e >= @mball     #一周するなら終わり
      y = g + @p_sum[@num][e]
      if inc?(y)                   #yが@p_sumに含まれていれば次の候補へ
        moving
        return
      end
      @p_sum[@num][listnum] = y
      listnum += 1
    end
  end
  
  if @num != @mball                #@path作成処理
    a = @path[@num] + 1
    @num += 1
    loop do                        #次に入れるべき数を探す
      break if not inc?(a)
      a += 1
    end
    @path[@num] = a
  else                             #全て埋まったら答えを保存
      @ans[@ansnum] = @a.dup
      @ansnum += 1
      moving                       #次の候補へ
  end
end


def inc?(number)                   #numberが@p_sumに含まれていればtrueを返す
  for i in 1...@num
    return true if @p_sum[i].include?(number)
  end
  return false
end


def ringing                        #主演算処理
  catch(:endflag){
  loop do
    x = @path[@num]
    if @num == @mball              #球の総和が@sumと一致するか確認
      y = @sum
      for i in 0..@mball
        y -= @a[i]
      end
      if y != x                    #一致しなければ次の候補へ
        @num -= 1
        moving
        next
      end
    end
    
    y = 0                          #入れる場所の候補を設定
    for i in 1..@mball             #i:球の位置
      if @a[i] == 0                #@a[i]に数が入っていなければ候補に加える
        @route[@num][y] = i
        y += 1
      end
    end
    
    @a[@route[@num][0]] = x        #一つ目の候補に数を入れる
    listing(@route[@num][0])       #入れた数を含む和のリストを作成
  end
  }
end


def moving                         #球の数の除去及び移動処理
  if not @route[@num] == []
    x = @a[@route[@num][0]]        #候補がまだあれば次の候補に数を移動
    @a[@route[@num][0]] = 0
    @route[@num].shift             #計算済みの候補を破棄
  end
  if @route[@num] == []            #無ければその数を除去する
    if @num == 1
      throw :endflag               #全ての候補を試したら演算終了
    else
      @p_sum[@num] = []
      @num -= 1
      moving
    end
  else
    @a[@route[@num][0]] = x
    listing(@route[@num][0])
  end
end


p main_ring(5)