Math, machine learning & cute things.

从 $1$ 到 $n$ 的正整数各出现两次，共 $2n$ 个数，分布在 $m\ (m\geq n)$ 个大小至多为 $2$ 的栈中。你可以进行至多 $\lceil \frac{3}{2}n \rceil$ 次如下操作：弹出一个栈的栈顶元素并压入另一个栈中，要求另一个栈是空的或该栈只有一个元素且该元素数值上等于要压入的元素。构造一个操作序列或报告无解，要求操作结束后的 $m$ 个栈满足栈要么为空要么恰包含两个相同的数。

$1 \leq n \leq m \leq 2 \times 10^{5}$。

主办方将在一个二维平面中投放广告。共有 $n$ 个广告可被投放，其中每个广告的都是左上角为 $(x_i,y_i)$ 的 $w\times h$ 矩形且出现时间为 $[l_i,r_i]$。同一时间内，任意两个被投放的广告不能有重叠面积。此外还有 $m$ 条限制 $(u_i,v_i)$ 表示在广告 $u_i$ 和广告 $v_i$ 中至少选择投放一条。判断是否存在一组合法的投放方案，如果存在的话给出方案。

$1\le n\le 5\times 10^4$，$1\le m\le 10^5$，$1\le w,h,x_i,y_i,l_i,r_i \le 2000$。

维护一棵点有颜色的树，一开始只有编号为 $1$ 的节点，其颜色为 $C$，要求支持以下操作 $q$ 次：

1. 给定 $x,c,d$，添加一个编号为 $n+1$ 颜色为 $c$ 的节点，向点 $x$ 连一条长度为 $d$ 的边
2. 给定 $x,c$，将点 $x$ 的颜色变成 $c$。

每次操作后，你都需要在树上选两个颜色不同的点并最大化它们之间最短简单路径的长度，并输出。

$1\le q\le 5 \times 10^5$。

定义一个排列 $P$ 上的操作 $(t,S)$ 为：

1. 有两个空序列 $A$ 和 $B$；
2. 枚举 $S_i=1$ 的每个 $i$：如果 $P_i$ 是偶数，则将其放到 $A$ 的末尾；否则放到 $B$ 的末尾；
3. 如果 $t=0$ 则令 $C=\overline{AB}$，否则令 $C=\overline{BA}$；
4. 枚举 $S_i=1$ 的每个 $i$：将 $P_i$ 替换为 $C$ 的开头元素，删去 $C$ 的开头元素。

现给定排列 $P$，要求使用至多 $30$ 次如上操作，使 $P$ 从小到大排序，注意你不需要最小化操作次数。

$1\le n\le 15000$。

给一个长度为 $n$ 的序列 $a_i$，和 $q$ 组询问 $(l,r,x)$，表示求 $\displaystyle\prod_{i=l}^r\left(1-\frac{a_i}{x}\right)$ 的值。实数输出，精度要求 $10^{-6}$。

$n,q\le6\times10^5,\ 1\leq a_i < x\leq 10^9$。