PS:此题目与类似的CF1196D2唯一的不同之处在于数据的范围。
给你$q$组询问（$1 \le q \le 2000$）
每组询问会先给你一个$n$和一个$k$（$1 \le k \le n \le 2000$）
下一行是一个字符串$s$（数据保证$s$只由大写字母$R$、$G$、$B$组成，输入数据保证所有$s$的长度和$ \le 2000$）
现在问你最少修改多少次$s$中的字母（一次只能修改一个字母），才能使得$s$的某一个子串是字符串$RGBRGBRGB...$的子串，同时该子串的长度$ \ge k$。
给定一个含有 $n$ 个点的有根树和一个长度为 $n$ 的排列 $p$，你需要给这棵树的每一条边赋权，使得对于所有的 $1 \leq i<j \leq n$，点 $p_{i}$ 到根的距离小于点 $p_{j}$ 到根的距离。
你需要保证每条边的边权都是 $[1,1 \times 10^{9}]$ 内的整数。
多组数据。若无解，输出 $-1$。否则输出 $n$ 个整数，第 $i$ 个整数 $w_{i}$ 表示点 $i$ 到其父亲的边权为 $w_{i}$，特别地，默认根到其父亲的边权为 $0$。
Translated by @HPXXZYY.
平面上有n个点，第i个点在（xi，yi）处
小t想绘制一个矩形区域（如下图
该矩形被其左侧、底部和右侧的三条线围起：x=l，y=a和x=r(l, r, a 都可以为实数并且l<r)。
求可能有多少种不同的非空点集可以被小t的矩形覆盖，我们认为两个集合不同是在一个集合中存在一个点而不在另一个集合中存在。
有一种用 $n \times n$ 的网格玩的游戏。
当 $(i,j)$ 填的是 L 时，你会走到 $(i, j - 1)$；
当 $(i,j)$ 填的是 R 时，你会走到 $(i, j + 1)$；
当 $(i,j)$ 填的是 U 时，你会走到 $(i - 1, j )$；
当 $(i,j)$ 填的是 D 时，你会走到 $(i + 1, j)$；
当 $(i,j)$ 填的是 X 时，你将不动。
当你从 $(i, j)$ 出发，最后将会停止在 $(x_{(i, j)}, y_{(i, j)})$。或者，如果你永远不会停止，$(x_{(i, j)}, y_{(i, j)})$ 是 $(-1, -1)$。
现在给出所有的 $(x_{(i, j)}, y_{(i, j)})$，试构造出原网格。如果无法构造，输出 INVALID，否则输出 VALID，并输出一种合法网格。
给定一棵 $n$ 个点的无根树，要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值，以及最多可以使用多少种不同权值。
这里，填入的边权值可以为任意大。
$3 \le n\le 10^5$