Rikka 拥有一棵包含 $n-1$ 个内部节点和 $n$ 个叶子节点的区间树。每个节点都关联着一个非空的整数区间。根节点关联的区间为 $[1, n]$。对于任何关联区间为 $[l, r]$ 的内部节点，存在一个整数 $m$，使得其左孩子关联的区间为 $[l, m]$，右孩子关联的区间为 $[m+1, r]$。

初始时，所有节点均为白色。Rikka 可以对区间执行一些查询。当她对区间 $[A, B]$ 执行查询时，对于满足以下条件的每个节点 $u$，从根节点到节点 $u$ 的路径（包含 $u$）会被染成黑色。条件如下：

• 节点 $u$ 关联的区间 $[l, r]$ 完全包含在 $[A, B]$ 中（形式化地，$A \le l \le r \le B$），并且
• 要么 $u$ 是根节点，要么 $u$ 的父节点关联的区间 $[l', r']$ 没有完全包含在 $[A, B]$ 中。

给定所有节点的最终颜色，求 Rikka 为了使所有节点达到给定颜色所需执行的最少查询次数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 4000$)。

接下来的 $(2n-1)$ 行描述了区间树的节点，每行一个。节点按前序遍历顺序描述：第一个描述的节点是根节点；对于每个内部节点，其描述紧随其后的是其左子树的描述，接着是其右子树的描述。

对于内部节点，该行包含两个整数 $t_i$ 和 $m_i$。对于叶子节点，该行包含一个整数 $t_i$。如果 $t_i = 1$，则节点为黑色；如果 $t_i = 0$，则节点为白色。保证每个 $t_i$ 均为 0 或 1。

对于关联区间为 $[l, r]$ 的内部节点，其左孩子关联区间为 $[l, m_i]$，右孩子关联区间为 $[m_i+1, r]$。保证输入描述的是一棵合法的区间树。特别地，如果节点 $i$ 是关联区间为 $[l, r]$ 的内部节点，则 $m_i$ 满足 $l \le m_i < r$。

输出格式

输出一个整数：使所有节点达到给定颜色所需的最少查询次数。如果无法按要求对节点着色，则输出字符串 “OwO”。

样例

输入 1

2
1 1
1
1

输出 1

2

输入 2

2
0 1
1
1

输出 2

OwO

输入 3

9
1 5
1 3
1 2
1 1
0
1
1
1 4
0
0
1 7
1 6
1
0
1 8
1
0

输出 3

2