考虑经典的俄罗斯方块游戏，二维平面上有若干个积木，他们会受重力的影响下落并堆叠。注意，积木只会竖直下落，如果下落过程中碰到了别的积木那么就会停下。例如下图：
不同颜色的块代表了不同的积木，这些积木下落之后会形如下图：
积木的形状可以任意的，可能跟传统的俄罗斯方块有一些不同，比如下图：
这张图中的积木下落后应该是这样的：
本题中，我们分别用
#和.表示有/无积木覆盖。为了方便起见，我们认为一个四联通块是一块积木。对于两个有积木覆盖的位置，如果他们共用一条边，则我们认为他们相邻，相邻的块构成的连通块被称为四联通块。在本题中，有一个给定的坐标 \((R,C)\)（第 \(R\) 行第 \(C\) 列，1下标），保证这个坐标一定被积木覆盖，你需要计算对于所有的
.替换成#的情况（注意，此时的四联通块可能会有变化），这个给定的坐标内的#下落到哪个坐标。同时为了不让输出成为时间瓶颈，你只需要输出一个验证码即可。具体来说，如果平面内有 \(k\) 个
.，他们的坐标分别是 \((r_1,c_1),(r_2,c_2),...,(r_k,c_k)\)（满足从左上到右下，即\((\forall i)(\forall j)(i\in \mathbb{N} \bigwedge j\in \mathbb{N}\land 1\leq i<j\leq k \rightarrow r_i<r_j \bigvee(r_i=r_j\land c_i<c_j))\)。将把仅 \((r_i,c_i)\) 替换成#后 \((R,C)\) 下落到的坐标记为 \((R_i,C_i)\)，则你需要输出 \((\sum_{i=1}^{k} R_i\times 2021^{k- i}) \bmod 998244353\)。(\(\bmod 998244353\) 即对 \(998244353\) 做除法之后的余数）对于所有数据，\(1\leq n\times m\leq 10^7\), \(1\leq R\leq n\), \(1\leq C\leq m\), 保证\((R,C)\)的位置是'#'。
非常好的一道题
先考虑 \(nm \leq 2000\) 的部分，考虑模拟下落过程，设 \(d_i\) 表示第 \(i\) 块下落距离。
考虑同一列上两个相邻的 # ，设他们所在连通块分别为 \(u,v\) ，则显然我们要求 \(d_u \leq d_v + l - 1\) ，其中 \(l\) 两个 # 间隔距离
这是什么？差分约束！直接建图跑最短路，复杂度 \(O((nm)^2 \log nm)\)
显然可以优化，因为当在图中加入一个 # 无非就是加入至多 \(4\) 条边和一个点
但我们要求的还是从超级源 \(S\rightarrow (R,C)\) 的最短路。我们为什么不从 \(S\) 跑一边最短路， \((R,C)\) 跑一边最短路，然后合并呢？
复杂度优化成了 \(O(nm \log nm)\)
继续优化，我们要想尽办法把 \(\log\) 去掉。发现复杂度瓶颈在 dijkstra
这时候突然想起luogu上一个水帖：把边权为 \(w\) 的边拆成 \(w\) 个为 \(1\) 的边跑 bfs 复杂度就变成 \(O(n)\) 了
我们也考虑这么拆点，因为 \(l \leq \max(m,n)\) ，而且这个图我们显然可以建成一个网格图，复杂度是不变的。于是我们有以下建图思路：
相邻的两个 # 之间连 \(0\) 边，. 和 . 之间连 \(1\) ，# 在 . 上方时连 \(1\) ，下方连 \(0\) 。最终跑 01bfs 。复杂度 \(O(nm)\)