This is an interactive problem.

给出一个 $n$ 个点 $m$ 条边的有向无环图（DAG）。你会得到该 DAG 的结构，但不会知道 DAG 中每条边的边权。

在任意一对顶点 $s$ 与 $t$ 之间可能存在多条路径，我们将一条路径的权值定义为该路径上所有边权的乘积。记 $f(s, t, c)$ 表示从 $s$ 到 $t$ 的所有不同路径，在所有边权都乘以 $c$ 情况下的权值之和，对 $998244353$ 取模。

你可以进行至多 $999$ 次询问，每次询问你需要给出参数 $s, t, c$，交互器会返回 $f(s, t, c)$ 的值。

最后，交互器会给出一个参数 $k$，你需要确定 $f(1, n, k)$ 的值。

数据范围：$1 \leq n \leq 10^3$，$1 \leq m \leq 5 \times 10^3$。

时空限制：$3$s / $1024$MiB。

Alice 和 Bob 正在玩取石子游戏。

有 $n$ 个房间，第 $i$ 个房间中有 $k_i(k_i \geq 1)$ 堆石子。Alice 和 Bob 轮流操作，Alice 先手。

每次操作时，玩家必须在当前房间中，选择任意一个非空的堆，然后在该堆中取出任意一个石子。只有在当前房间中将所有石子取完，Alice 和 Bob 才可以到下一个房间继续进行游戏。若某位玩家无法进行操作（即到了最后一个房间并且房间为空），则该玩家输掉游戏。

在游戏开始前，Alice 可以决定房间的访问顺序，访问顺序可以用一个排列 $p$ 描述，表示依次经过房间 $p_1, p_2, \dots, p_n$，只有房间 $p_i$ 没有石子的情况下，才可以去房间 $p_{i + 1}$。

假设 Alice 和 Bob 进行的都是最优决策，Alice 想知道他有多少种排列 $p$ 可以获胜。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 10^6$，$1 \leq \sum k_i \leq 10^6$，石子数量 $\in [1, 10^9]$。

时空限制：$1$s / $512$MiB。

有 $n$ 座金矿排成一行，每座金矿有一个属性 $a_i$，表示该金矿一天产出的金币数量。每座金矿都潜伏着一只有属性 $b_i$ 的哥布林，代表该哥布林的贪婪值。

每天夜晚都会发生以下的事件：你将从第 $1$ 座金矿走到第 $n$ 座金矿，初始金币为 $0$，每走过一座金矿 $i$，以下两件事情依次发生：

• 你将获得 $a_i$ 金币。
• 哥布林向你索要 $b_i$ 金币，若你没有 $b_i$ 金币则需要将所有金币交给哥布林。

你需要在这里 $m$ 天，每天都会进行以下操作中的一种：

• 1 x y：令 $a_x = y$，修改是持久的。
• 2 x y：令 $b_x = y$，修改是持久的。
• 3 x：版本回到第 $x$ 天。
• 4 k p1 p2 ... pk：有 $k$ 个位于金矿 $p_1, p_2, \dots, p_k$ 的哥布林向你索要金币的方式变为“若你目前拥有 $s$ 金币，它们将要向你索要 $\left\lceil \frac{s}{2} \right\rceil$ 金币”，变化是临时的。你需要求出当晚要交给哥布林多少金币。

有 $n$ 种物品，其中第 $i$ 种物品的重量为 $w_i$，每一种物品的数量都是无限的。

是否能恰好选 $n$ 个物品，使得所选物品的重量之和为 $m$。

数据范围：$1 \leq n \leq 10^5$，$0 \leq m \leq n^2$，$0 \leq w_i \leq n$。

时空限制：$8$s / $1024$MiB。

This is an interactive problem.

一个机器人在一个无限大的二维平面的第一象限内移动。最初机器人位于坐标 $(s_x, s_y)$。最初所有单元格都是白色的。

游戏包含了若干次操作，最多 $T = 1000$ 次操作。每次操作都会按照以下顺序发生事件：

1. 你的操作：你可以选择一个整点坐标 $(x, y)$，其中 $1 \leq x, y \leq T$，你会将该单元格标记成黑色。
2. 机器人的操作：机器人可以移动到与其所在单元格八连通的单元格（由交互器决策）。
3. 结果检查：机器人移动到下一个单元格之后，系统会检查该单元格是否是黑色。

• 如果是黑色，机器人爆炸。
• 如果是白色，则进行下一次操作。

你的目标是在 $T$ 次操作之内使机器人爆炸。

数据范围 $1 \leq s_x, s_y \leq 20$。

时空限制：$2$s / $1024$MiB。

给出一个长度为 $n$ 的数组 $a$，其中数组中的元素均为 $1 \sim m$ 中的正整数。

你需要找到四个不同的索引 $p, q, r, s$，使得 $\gcd(a_p, a_q) = 1$ 且 $\gcd(a_r, a_s) = 1$。

数据范围：$4 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^6$，$1 \leq a_i \leq m$。

时空限制：$3$s / $256$MiB。

有 $n$ 个点，第 $i$ 个点的初始坐标为整点 $(x_i, y_i)$。

接下来有 $m$ 轮移动，每一轮中的所有 $n$ 个点 $(x, y)$ 都需要移动到 $(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)$ 四个位置的其中一个。

你需要求出有多少种不同的移动点的方式，使得最终 $n$ 个点两两曼哈顿距离小于等于 $k$。其中 $(x_1, y_1), (x_2, y_2)$ 的曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$。

数据范围：$1 \leq n \leq 50$，$1 \leq m \leq 10^5$，$0 \leq k \leq 10$，$0 \leq |x_i|, |y_i| \leq 10^5$。

时空限制：$2$s / $1024$MiB。

给出一棵包含 $n$ 个点的树，每个节点有一种颜色 $c_i$。

有 $m$ 次查询，每次查询给出三个参数 $l, r, x$，表示询问只保留编号在 $[l, r]$ 范围内的点时，$x$ 所在连通块的颜色种类数。

数据范围：$1 \leq n, m \leq 10^5$，$1 \leq c_i \leq n$，$1 \leq l \leq x \leq r \leq n$。

时空限制：$1$s / $250$MiB。

对于一个包含字符串 $s_1, s_2, \dots, s_k$ 的字符串可重集 $T$，定义 $T$ 的价值为

$$\sum\limits_{1 \leq i < j \leq k} \mathrm{LCP}(s_i, s_j)$$

给出一个长度为 $n$ 的字符串 $S$，下标从 $1$ 到 $n$。有一个初始为空的字符串集合 $T$。

有 $m$ 次操作，每次操作给出两个正整数 $l, r(1 \leq l \leq r \leq n)$，你需要将字符串 $S[l : r]$ 的所有前缀都加入集合 $T$。形式化地，对于所有 $l \leq i \leq r$，你需要将 $S[l : i]$ 加入集合 $T$。

每次操作过后，你都需要求出此刻集合 $T$ 的价值。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n, m \leq 10^5$。

时空限制：$8$s / $512$MiB。

给出一棵包含 $n$ 个节点的树，以 $1$ 为根，边带权。

定义 $\mathrm{dep}_x$ 表示节点 $x$ 到根的简单路径上的边权和。

有 $Q$ 次查询，每次查询给出两个参数 $l, r$，对于所有满足 $l \leq i, j \leq r$ 的二元组 $(i, j)$，你需要求出有多少种不同的 $\mathrm{dep}_{\mathrm{LCA}(i, j)}$。

数据范围：$1 \leq n \leq 10^5$，$1 \leq Q \leq 5 \times 10^5$，$-10^9 \leq w \leq 10^9$，$1 \leq l \leq r \leq n$。

时空限制：$500$ms / $512$MiB。