暂无测试数据。

蒜头君的 OIer 好友共有 $n$ 个人。今天他们进行了一场知识探讨会议，$n$ 个人围绕圆形的会议桌依次落座，并按照顺时针给他们编号： $1,2,\cdots, n$。

每个人都有一个 $0/1$ 状态，表示他今天有没有刷题。第 $i$ 个人的状态使用 $state[i]$ 表示，如果他今天刷题了，则状态为 $state[i] = 1$，否则状态为 $state[i] = 0$。当然，因为参加会议的都是大佬，所以每个人刷题的状态会受到当天定义的标准做题数量发生改变。

现在要从 $1$ 号 OIer 开始，每个人依次都会在环上选择一个区间（自己也可以在这个区间内），并对该区间内每个人的做题状态进行修改。修改的规则为：首先要计算出自己的做题状态异或 $1$ 的结果 k = state[i] ^ 1;，然后将选择的区间内所有人的做题状态修改为 $k$。当所有人都对区间进行修改后，每个人的做题状态就固定了。

已知蒜头君的编号为 $s$。他已经预先得知了其他 $n-1$ 个 OIer 要选择的区间。他需要根据其他人的选择方案，自己选择一个最优的区间，使得最后每个人的做题状态中做题（状态为 $1$）的人数最多。

但是蒜头君还需要出题，所以希望你，OI 界的希望，帮他计算一下最优的区间选择方案。

输入格式

第一行输入两个以空格隔开的正整数 $n,s$，表示参加会议的 OIer 的人数和蒜头君的编号。

第二行输入 $n$ 个以空格隔开的整数 $state[1],\cdots state[n]$，表示每个 OIer 初始的做题状态。如果第 $i$ 个人今天刷题了，则状态为 $state[i] = 1$，否则状态为 $state[i] = 0$。

接下来 $n-1$ 行，每行输入两个以空格隔开的整数 $l_i,r_i$，表示从 $1$ 号 OIer 开始，除了蒜头君外每个 OIer 选择的区间。该区间即为从 $l_i$ 顺时针转到 $r_i$（包括 $l_i,r_i$）经过的所有人。注意 $l_i$ 可以大于 $r_i$。

输出格式

第一行一个整数，表明最后每个人的做题状态中最多做题（状态为 $1$）的人数。

第二行输出两个以空格隔开的整数 $l,r$，表示蒜头君要选择的最优区间方案，为从 $l$ 顺时针到达 $r$。若有多解，输出任意一组。注意蒜头君必须选择一个合法区间。

数据范围

对于 $10\%$ 的数据，$n \le 80$。

对于 $30\%$ 的数据，$n\le250$。

对于 $50\%$ 的数据，$n\le3000$。

另有 $10\%$ 的数据，$s=n$ 。

对于 $70\%$ 的数据，$n\le10^5$。

对于 $100\%$ 的数据，$1\le n\le2\times 10^6,1\le s,l_i,r_i\le n,state[i]\in[0,1]$。

提示

本题输入数据规模较大，请选手使用较为快速的读入方式。

给出读入优化模板：

inline int rd() {
    int ret;
    char ch;
    for(; (ch = getchar() - '0') < 0 || ch > 9;);
    for(ret = ch; (ch = getchar() - '0') >= 0 && ch <= 9; ret=(ret << 3) + (ret << 1) + ch);
    return ret;
}

4 3
1 1 0 1
4 1
4 4
1 2

3
3 3