#1475. [L3-1] 不连续的存在

救世主大人在和莉露露酱对电波，一共交流了 $m$ 个片段。

进行一组电波上的片段交流的过程十分复杂。简而言之，分为以下三个步骤。

首先，取一个 $n \times n$ 的矩阵 $A$，其行列下标从 $1$ 开始编号，其中第 $i$ 行第 $j$ 列的元素为 $(i-1)\times n+j$，例如，$n=4$ 时有：

$$A = \begin{bmatrix} 1&2&3&4\\ 5&6&7&8\\ 9&10&11&12\\ 13&14&15&16 \end{bmatrix}$$

多么美丽的矩阵啊！它象征着“上帝”。

其次，救世主大人会“创造”一个“妄想”，用一个 $n$ 维列向量 $c^0$ 表示。

接着，作为上帝的使者，莉露露酱会给出一个 $L$ 长的 $01$ 序列 $s$。对于其第 $k$ 个位置上的值：

• 如果其为 $0$，说明通信正常，救世主将会将“上帝”（矩阵 $A$）左乘在自己当前的“妄想”（列向量 $c^k$）上；
• 否则，表明通信被“暗黑波动的源头”所干扰，救世主将会将“上帝”的逆位（矩阵 $A$ 的转置）左乘在自己的当前“妄想”上。

即：

$$c^{k+1} = \begin{cases} A\times c^k&s[k]==0\\ A^T\times c^k&s[k]==1\\ \end{cases}$$

最后得到的“妄想”（$c^L$）的值就是本次交流的结果。

由于连续交流了 $m$ 个片段，那么我们可以知道第 $i$ 个片段最初的“妄想” $c^0_i$ 是上一个片段最终的结果 $c^{L_{i-1}}_{i-1}$。特别地第一个片段的最初“妄想”会单独给出。

对于第 $i$ 个片段，$s_i$ 将会是是某个 $01$ 序列 $T$ 的子串 $T[l_i:r_i]$。

由于救世主的脑容量有限，请输出对 20180720 取模的结果。

第一行是三个正整数 $n,m,L$，分别表示“妄想”的维度、交流的片段数、$01$ 序列 $T$ 的长度；

第二行是 $n$ 个整数，表示第一个片段最初的“妄想” $c^0_0$；

第三行是一个长 $L$ 的 $01$ 序列 $T$；

接下来 $m$ 行，每行给出两个正整数 $l_i$ 和 $r_i$，表示这个片段莉露露酱给出的 $01$ 序列是 $T[l_i:r_i]$ 部分。

共一行，$n$ 个整数，表示最终的结果。

样例输入

2 2 3
1 2
110
2 3
2 2

样例输出

210 298

样例解释

$$\begin{bmatrix} 1&2\\ 3&4\\ \end{bmatrix} \times \begin{bmatrix} 1&3\\ 2&4\\ \end{bmatrix} \times \begin{bmatrix} 1\\ 2\\ \end{bmatrix} =\begin{bmatrix} 27\\ 61\\ \end{bmatrix}\\$$

$$\begin{bmatrix} 1&3\\ 2&4\\ \end{bmatrix} \times \begin{bmatrix} 27\\ 61\\ \end{bmatrix} =\begin{bmatrix} 210\\ 298\\ \end{bmatrix}\\$$

对于所有测试数据，满足：

$1\le n,m,L \le 2\times 10^5$；

$1\le l_i \le r_i \le L$；

$0\le c_i\le 10^7$。

tips: 世界的意义必定在世界之外。

UPDATE (20250331): 素晴日 15 周年版将于今年 7 月 20 日上线。