U253643 数字三角形

**注意：std 不开 O2 可过，本题不卡常。请不要开 O2 过。本题时限是 std 的 1.6 倍以上。** 2025-04-16：无意中找到 oeis【A173395】。

给定一个如下的数字三角形，共有无限行。 其规律是：第 $i$ 列是公差为 $i+1$ 的等差数列，首项为 $2i+2$。 ``` 4 6 6 8 9 8 10 12 12 10 12 15 16 15 12 14 18 20 20 18 14 16 21 24 25 24 21 16 18 24 28 30 30 28 24 18 20 27 32 35 36 35 32 27 20 22 30 36 40 42 42 40 36 30 22 24 33 40 45 48 49 48 45 40 33 24 ... ``` 记数字三角形第 $i$ 行，第 $j$ 列的数字为 $a_{i,j}$。例如，第 $7$ 行，第 $3$ 列的数字为 $24$。一个数 $x$ 存在于数字三角形，当且仅当存在数对 $(i,j)$，使得 $a_{i,j}=x$。 需要注意的是，数字三角形中有很多重复的数字，也有一些数字不存在。 现在，Yurchiu 和 $\tt{zz}\omega$ 给出 $Q$ 个询问，你均需要快速地回答。 询问一共有四种，分别是： 1. Yurchiu 想要知道第 $x$ 行的和。答案对某个正整数 $p$ 取模。本询问分数占 $15\%$。 2. 给定一个大于 $4$ 的正整数 $y$。如果不存在于数字三角形中，回答 `-1`。否则，显然这个数字可以由一个或多个数对 $(i,j)$ 对应（即使得 $y=a_{i,j}$）。分别求 $\min\{a_{i+1,j+1}\}$ 和 $\max\{a_{i+1,j+1}\}$ 。Yurchiu 想要知道这个问题的答案。显然，$a_{i+1,j+1}$ 一定存在。本询问分数占 $21\%$。 3. 给定一个坐标 $(b,d)$，其对应 $a_{b,d}$。保证 $b\ge d$。以这个坐标为起点，连续走 $k$ 步。$\tt{zz}\omega$ 想要分别知道可走到的最大值和最小值。“走一步”定义为使横坐标或纵坐标加一或减一（横纵坐标同时最多加或减一个），且保证走到的坐标合法。本询问分数占 $29\%$。 4. 给定一个大于 $4$ 的正整数 $z$。如果不存在于数字三角形中，回答 `-1`。否则，回答 $\min\{a_{i,j-1},a_{i,j+1}\}$ 的最小可能值。Yurchiu 想要知道这个问题的答案。特别地，在本询问中，如果 $a_{i,j-1}$ 或 $a_{i,j+1}$ 不存在，则认为它的值为 $+\infty$。本询问分数占 $35\%$。

第一行包含两个整数 $Q$ 和 $type$，表示询问的个数和询问类型。 接下来 $Q$ 行。对于询问 2 和 4，每行一个整数。对于询问 1，每行两个整数。对于询问 3，每行三个整数。

输出 $Q$ 行。对于询问 1 和 4，每行一个整数。对于询问 2 和 3，每行两个整数。 特别地，如果答案是 `-1`，那么本行一个整数 `-1`。

【样例解释】 样例 #2：第一个询问，$12$ 对应的数对有 $4$ 个，$a_{i+1,j+1}$ 的值可以是 $14$，$15$，$16$，$18$。 样例 #3：第二个询问，给定坐标对应的数是 $24$。向右走一步就可以到达最大值 $28$，向左走一步就可以到达最小值 $18$。 样例 #4：第二个询问，$16$ 对应的数对有 $3$ 个，$(a_{i,j-1},a_{i,j+1})$ 可以是 $(+\infty,21)$，$(15,15)$，$(21,+\infty)$。六个数中，最小的是 $15$。注：表示成括号的形式是为了方便理解，以上六个数是独立的。 【数据范围】 **测试点不等分**。对于每种询问，均有： - 对于 $50\%$ 的数据，满足 $1\le Q\le {10}^3$。 - 对于 $100\%$ 的数据，满足 $1\le Q\le 5\times10^5$。 特别地： - 对于询问一，$1\le x,p\le 10^{16}$。对于 $50\%$ 的数据，$1\le x\le 10^3$。**注意，$p$ 不保证是质数。** - 对于询问二，$5\le y\le 5\times10^6$。 - 对于询问三，$1\le b,d,k\le10^7$。对于 $50\%$ 的数据，$1\le k\le 50$。 - 对于询问四，$5\le z\le 5\times10^6$。 【本题来源】 - Idea：Yurchiu，$\tt{zz\omega}$。 - 其余：Yurchiu。 题解等资源可以看 Yurchiu 的最后一次提交，内有链接。