人工神经网络（通常简称为神经网络）是一种受生物神经网络启发的数学模型。神经网络由一组相互连接的人工神经元组成，并使用联结主义方法进行计算。

如果神经网络的神经元被组织成若干组，称为“层”，则称该神经网络为分层神经网络。同一层内的两个神经元之间没有连接。

我们将神经元按顺序编号为从 $1$ 到 $q$ 的正整数，其中 $q$ 是网络中神经元的数量。神经元 $i$ 和神经元 $j$ 之间的连接可以用连接权重 $w_{i,j}$ 来描述。

神经网络可以表示为一个有向无环图：神经元由顶点表示，神经元之间的连接由边表示。每个连接的权重可以表示为相应边的权重。

上图展示了一个由四层组成的神经网络。第一层包含神经元 $1, 2, 3$，第二层包含神经元 $4, 5$，第三层包含神经元 $6, 7, 8$，第四层仅包含神经元 $9$。

每个神经元 $i$ 都有一个值 $v_i$，该值由以下公式计算得出：

$$v_i = \frac{1}{1 + e^{-\sum_j v_j \cdot w_{j,i}}}$$

如果分层神经网络具有以下属性，则称为二元神经网络：

• 对于第一层的每个神经元 $i$，其值 $v_i$ 为 $0$ 或 $1$；
• 如果神经元 $a$ 属于第 $i$ 层，神经元 $b$ 属于第 $j$ 层且 $i > j$，则不存在从神经元 $a$ 到神经元 $b$ 的连接。注意，从神经元 $b$ 到神经元 $a$ 的连接仍然是可能的；
• 最后一层仅包含一个神经元，其值要么为 $0$，要么为 $1$；
• 每一层至少包含一个神经元。

在本题中，你需要创建一个二元神经网络来实现具有 $n$ 个参数的二元函数 $f(x_1, x_2, \dots, x_n)$。

该二元神经网络的第一层应包含恰好 $n$ 个神经元，编号为从 $1$ 到 $n$ 的连续正整数。神经元 $i$ 的值将自动设置为 $x_i$。所有其他神经元应编号为从 $n+1$ 到 $q$ 的连续正整数，其中 $q$ 是网络中神经元的数量。所有值 $v_i$ ($n+1 \le i \le q$) 将根据上述公式计算。

该二元神经网络的最后一层应仅包含一个神经元。该神经元的值与 $f(x_1, x_2, \dots, x_n)$ 的值之差不得超过 $10^{-7}$。

该二元网络包含的层数不得超过 $25$ 层。神经元数量 $q$ 不得超过 $10^4$。连接总数 $e$ 不得超过 $3 \cdot 10^4$。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 10$)。第二行包含 $2^n$ 个字符。每个字符要么是 '0'，要么是 '1'。第一个字符描述 $f(0, \dots, 0, 0)$ 的值，第二个字符描述 $f(0, \dots, 0, 1)$ 的值，依此类推，最后一个字符描述 $f(1, \dots, 1, 1)$ 的值。

输出格式

第一行输出两个整数 $l$ 和 $q$ —— 分别为二元神经网络的层数和神经元数量 ($2 \le l \le 25, 1 \le q \le 10^4$)。

第二行输出 $q$ 个整数 $p_i$。其中 $p_i$ 是神经元 $i$ 所属的层号 ($1 \le p_i \le l$)。

第三行输出一个整数 $e$ —— 二元神经网络中的连接数 ($n \le e \le 3 \cdot 10^4$)。

接下来的 $e$ 行，每行包含两个整数 $a_i, b_i$ 和一个实数 $w_{a,b}$ —— 描述从 $a_i$ 到 $b_i$ 的连接及其权重 $w_{a,b}$ ($|w_{a,b}| \le 1000$)。

样例

输入 1

3
00010111

输出 1

3 7
1 1 1 2 2 2 3
12
1 4 8.906
1 5 0.749
1 6 5.423
2 4 -0.262
2 5 -8.905
2 6 5.582
3 4 -0.663
3 5 1.087
3 6 -12.123
4 7 66.372
5 7 -55.329
6 7 -47.883