最近，你前往安戈洛（Un’Goro）旅行。

安戈洛的一条小路吸引了你的注意。这条路包含 $n$ 个台阶，每个台阶都被涂成红色或蓝色。

当你从第 $i$ 个台阶走到第 $j$ 个台阶时，你会计算你经过的红色台阶的数量。如果这个数量是奇数，你就会感到满意。

你感到好奇：“有多少对 $(i, j)$ ($1 \le i \le j \le n$)，使得我从第 $i$ 个台阶走到第 $j$ 个台阶时会感到满意？”此外，如何构造所有使得该对数达到最大的染色方案？

输入格式

仅一行，包含一个整数 $n$ ($1 \le n \le 10^5$)，表示道路的台阶数。

输出格式

第一行输出一个整数，表示让你满意的最大对数。

接下来若干行，每行包含一个长度为 $n$ 的字符串，表示一种染色方案，按字典序升序排列。第 $i$ 个字符表示第 $i$ 个台阶的颜色，其中 r 代表红色，b 代表蓝色。

如果存在超过 100 种不同的染色方案，只需找出字典序最小的 100 种。

注意，在字典序中，b 排在 r 之前。

样例

样例输入 1

1

样例输出 1

1
r

样例输入 2

2

样例输出 2

2
br
rb
rr

样例输入 3

3

样例输出 3

4
brb
rbr
rrr