该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

地面上有 $n$ 条源石矿脉，每条源石矿脉开采一次可以获得 $a_i$（$i\in[1,n])$ 个源石，每条源石矿脉含有的源石是无限的。小红和小蓝一起来开采源石矿，他们都想获得更多的源石，于是他们制定了一个游戏规则。

首先，小蓝和小红会一起开采 $q$ 次源石矿脉，每次从 $l\sim r$ 号矿脉中对其中的产量前 $2$ 大的源石矿脉进行一次开采。例如 $a=[1,2,2,3,4],l=1,r=3$，则他们这一次开采可以获得 $2+2=4$ 个源石。

当他们开采完后，将所有开采到的源石堆放在一起，此时一共有 $\text{sum}$ 个源石。现在，小红和小蓝决定，他们每人轮流从开采出的源石中拿出源石，每人每次至少拿一个源石，最多拿 $m$ 个源石，谁取走了最后一块源石，谁就可以掌握本次开采出的源石的分配权。

当小蓝和小红都是在最优决策下，由 小红先手，最终谁能获得源石的分配权呢？

如果是小红获得，第一行输出 $\text{sum}$，第二行输出 red；如果是小蓝获得，第一行输出 $\text{sum}$，第二行输出 blue。

输入格式

第一行输入 $2$ 个正整数 $n$ 和 $q$，含义如题所述。

第二行输入 $n$ 个正整数 $a_1, a_2, \dots , a_n$（$1\leq a_i \leq 10^8$），表示序列 $a$。

接下来 $q$ 行，每行输入 $2$ 个正整数 $l,r$（$1\leq l < r \leq n$），代表需要开采的区间。

最后一行输入一个正整数 $m$（$1\leq m \leq 14$），含义如题所述。

输出格式

输出 $2$ 行，第一行输出开采完成的 $\text{sum}$ 个源石，第二行输出一个字符串，如果是小红获胜输出 red；如果是小蓝获胜输出 blue。

样例输入输出

5 3
1 2 2 4 5
1 2
1 5
1 3
7

16
blue

样例说明

对于样例，三次开采之和为 $1+2+4+5+2+2=16$。可以证明在最多取 $7$​ 个的情况下，无论如何博弈，小蓝都有必胜的方式。

评测用例规模与规定

对于$10\%$的数据，$2\leq n \leq 200,1\leq q \leq 1000$。

对于$100\%$的数据，$2\leq n \leq 2\times 10^5,1\leq q \leq 10^5$。

运行限制

• 最大运行时间：$1s$
• 最大运行内存：$512M$