碎屍萬段是一個幾何題技巧，顧名思義就是把題目中的幾何物件切成許多份。其中一個最常見的途是把圓轉成正很多邊形，就能用現有的多邊形方法去解決這些問題。

不過顯然這個方法有很多誤差問題，跑得也比較慢，而且出題者大多都很聰明，所以這個技巧很難在實際的地方用上。

可是今天不一樣，你要碎屍萬段的目標是一顆超立方蛋糕。

現在你手邊有的是 $n$ 維的超立方蛋糕，
如果把 $n$ 維空間中的點座標化成 $(x_1, x_2, \ldots, x_n)$，那 $n$ 維的蛋糕可以這樣想像：

• $2 ^ n$ 顆頂點，在座標為 $\{\pm 1\} ^ n$ 的地方。
• $n \cdot 2 ^ {n-1}$ 條邊，在所有座標只有一個維度不一樣的點對之間。
• 蛋糕本體是 $\{(x_1, \ldots, x_n) \mid -1 \leq x_i \leq 1, \forall 1 \leq i \leq n\}$ 的集合。

每一刀當然也是 $n$ 維的超平面，也就是由 $a_1, a_2, \ldots, a_n, c$ 這 $n + 1$ 個參數所決定，表示這一刀會把所有
$a_1x_1 + a_2x_2 + \cdots + a_nx_n < c$ 跟 $a_1x_1 + a_2x_2 + \cdots + a_nx_n > c$ 的所有蛋糕都分開。
切在中間（也就是 $a_1x_1 + a_2x_2 + \cdots + a_nx_n = c$ ）的不算，因為它會黏在刀子上。

你的目標是用最少的刀數切過所有的邊，也就是說所有 $n \cdot 2^ {n-1}$ 條邊，兩端的頂點都至少被某一刀切在兩邊。