题目描述

你准备去山里进行一次长途徒步。徒步路线长度为 $N$ 米。你已知 $N+1$ 个整数 $A_0,A_1,\ldots,A_N$，其中 $A_i$ 表示路线在第 $i$ 米处的海拔高度，单位为米。

你觉得在出发前需要更充分地准备。由于路线很长，手工分析会非常麻烦，因此你决定把徒步路线划分成若干个阶段。每个阶段可以是上升阶段、下降阶段或平坦阶段。

划分需要满足以下规则。设某个阶段的长度为 $\ell$。

• 每个上升阶段和每个下降阶段的长度都必须至少为 $M$ 米；
• 每个平坦阶段的长度都必须至少为 $1$ 米；
• 每个平坦阶段终点高度与起点高度的差的绝对值必须小于 $C$ 米；
• 每个上升阶段的终点必须比起点至少高 $C \cdot \ell$ 米；
• 每个下降阶段的终点必须比起点至少低 $C \cdot \ell$ 米；
• 任何上升阶段或平坦阶段，都不能包含一个子区间，使得该子区间单独看时是一个合法的下降阶段；
• 任何下降阶段或平坦阶段，都不能包含一个子区间，使得该子区间单独看时是一个合法的上升阶段；
• 两个相同类型的阶段不能直接相邻。

请找出一种合法划分，使得阶段数量最少。

输入格式

第一行包含整数 $N,M,P,Q$：

$$1 \le N \le 10^5,\quad 1 \le M \le N,\quad 1 \le P \le 10^9,\quad 1 \le Q \le 10^9,$$

其中 $C = \frac{P}{Q}$。

第二行包含 $N+1$ 个整数 $A_0,A_1,\ldots,A_N$：

$$0 \le A_i \le 10^9.$$

输出格式

如果无法把路线划分成满足条件的阶段，输出：

-1

否则，第一行输出阶段数量 $K$。接下来 $K$ 行，每行输出两个整数 $L_i$、$R_i$ 以及一个阶段类型，表示第 $i$ 个阶段的起点、终点和类型。

阶段类型必须是下列三种字符串之一：

• TOUSEV：上升阶段；
• LASKUV：下降阶段；
• TASANE：平坦阶段。

必须满足：

$$L_1 = 0,\quad R_K = N,$$

并且对每个 $1 \le i < K$，都有：

$$R_i = L_{i+1}.$$

样例 1

输入

7 3 3 2
2 0 4 1 3 7 8 10

输出

2
0 4 TASANE
4 7 TOUSEV

样例 2

输入

6 2 2 1
5 2 0 3 3 2 5

输出

-1

样例 3

输入

16 3 5 3
8 9 6 3 6 8 4 3 7 8 9 8 10 7 3 0 2

输出

5
0 3 LASKUV
3 7 TASANE
7 10 TOUSEV
10 12 TASANE
12 16 LASKUV

评分方式

本题测试点按组计分。只有通过某个分组中的所有测试点，才能获得该组分数。分组如下：

1.（0 分）题面中的样例。
2.（60 分）$N \le 100$。
3.（15 分）$N \le 1000$。
4.（25 分）无额外限制。

此外，分组 3 和分组 4 只有在程序也正确通过所有前置测试组时才会获得分数。