题目内容

某山区建立了一套应急救援通道网络。由于地形限制，从指挥中心（根节点）出发，每条通道在岔路口只能分为两条分支，最终抵达不同救援集结点（叶子节点）。

每个通道节点都有对应的海拔高度（米）。救援队从指挥中心出发前往集结点，需要权衡两方面安全因素：

• 体力消耗：上坡比下坡更耗体力。将每段路程的体力消耗定义为：
  • 上坡（海拔升高）：$\alpha \times |\text{高差}|$
  • 下坡（海拔降低）：$\beta \times |\text{高差}|$
  • 一条路线的总体力消耗为各段消耗之和
• 海拔跨度：路线上最高海拔与最低海拔的差值不能超过安全阈值 $S$，否则气压变化过大，队员有高原反应风险。

一条「路线」指从根节点出发、走到某个叶子节点的路径（叶子节点指左右子节点都不存在的节点）。你的任务是：在所有海拔跨度不超过 $S$ 的路线中，找出总体力消耗最小的路线。

若存在多条体力消耗相同的路线，选择节点编号序列字典序较小的那条：按顺序逐个比较两条序列的元素，第一个不同的位置上元素更小者更小；若一条序列是另一条序列的前缀，则较短的序列更小。

输入描述

输入包含一行，格式为 n,alpha,beta,S,nodes：

• 最前面是四个整数 $n, \alpha, \beta, S$，以逗号分隔；
• 之后是一个用方括号包裹的二维数组 nodes，共 $n$ 行，每行 4 个整数，以逗号分隔。

例如 7,3,1,800,[[1,2000,2,3],[2,1500,4,5],...]。逗号或方括号之后允许出现空格、制表符或换行（解析时需容忍任意空白），语义不变。

nodes[i] 描述第 $i$ 个节点，含义如下：

• nodes[i][0]：id，节点编号（$1 \sim n$ 的整数，$1$ 号节点永远是根节点）；
• nodes[i][1]：value，该节点海拔高度（米）；
• nodes[i][2]：left，左子节点编号（没有左子节点则为 -1）；
• nodes[i][3]：right，右子节点编号（没有右子节点则为 -1）。

数据范围与保证：

1. $3 \le n \le 10000$
2. $1 \le \alpha, \beta \le 10$
3. $1 \le S \le 4000$
4. $100 \le \text{value} \le 4000$
5. 节点按 id 升序给出（即 nodes[i][0] = i + 1），树结构合法：$1$ 号为根，每个非根节点恰有一个父节点，不存在环，且从根可达所有节点；叶子节点的判定是「left 与 right 同时为 -1」，只有单个子节点的节点不是叶子。
6. 单条路线的总体力消耗满足 $\alpha \times 9999 \times 3900 \le 3.9 \times 10^8$，在 32 位有符号整数范围内（实现时用 64 位中间量更稳妥）。

输出描述

输出恰好一行：

• 若存在合法路线，输出形如 [1,3,6] 的数组：路线经过的节点 id 序列（从根节点 $1$ 开始，到叶子节点结束），元素之间用逗号分隔且不含空格；
• 若不存在合法路线，输出空数组 []。

约定：本题统一用空数组 [] 表示「无安全路线 / 无合法路线」，不要输出 null、-1、无安全路线 等任何其它形式；输出末尾恰好一个换行符。

样例1

输入

7,3,1,800,[[1,2000,2,3],[2,1500,4,5],[3,2400,6,7],[4,900,-1,-1],[5,2300,-1,-1],[6,2100,-1,-1],[7,2800,-1,-1]]

输出

[1,3,6]

说明

          [1:2000]
         /        \
    [2:1500]      [3:2400]
     /     \       /      \
[4:900] [5:2300] [6:2100] [7:2800]

4 条路线的分析（$\alpha=3, \beta=1, S=800$）：

• 1->2->4：下 500（$\times 1=500$）+ 下 600（$\times 1=600$）= 1100；$2000-900=1100$，跨度超限
• 1->2->5：下 500（$\times 1=500$）+ 上 800（$\times 3=2400$）= 2900；$2300-1500=800$，合法
• 1->3->6：上 400（$\times 3=1200$）+ 下 300（$\times 1=300$）= 1500；$2400-2100=300$，合法
• 1->3->7：上 400（$\times 3=1200$）+ 上 400（$\times 3=1200$）= 2400；$2800-2000=800$，合法

1->2->4 虽然体力消耗最低（1100），但海拔跨度 1100 超过安全阈值 800，被淘汰；合法路线中 1->3->6 总消耗 1500 最小，故选之。

样例2

输入

3,1,1,100,[[1,2000,2,3],[2,1000,-1,-1],[3,3000,-1,-1]]

输出

[]

说明

   [1: 2000]
   /       \
[2: 1000] [3: 3000]

2 条路线分析（$\alpha=1, \beta=1, S=100$）：

• 1->2：海拔跨度 1000 > 安全阈值 100，不合法
• 1->3：海拔跨度 1000 > 安全阈值 100，不合法

故没有合法路线，按约定输出空数组 []。