CF1392G.Omkar and Pies

Omkar has a pie tray with $k$ ($2 \leq k \leq 20$) spots. Each spot in the tray contains either a chocolate pie or a pumpkin pie. However, Omkar does not like the way that the pies are currently arranged, and has another ideal arrangement that he would prefer instead.

To assist Omkar, $n$ elves have gathered in a line to swap the pies in Omkar's tray. The $j$-th elf from the left is able to swap the pies at positions $a_j$ and $b_j$ in the tray.

In order to get as close to his ideal arrangement as possible, Omkar may choose a contiguous subsegment of the elves and then pass his pie tray through the subsegment starting from the left. However, since the elves have gone to so much effort to gather in a line, they request that Omkar's chosen segment contain at least $m$ ($1 \leq m \leq n$) elves.

Formally, Omkar may choose two integers $l$ and $r$ satisfying $1 \leq l \leq r \leq n$ and $r - l + 1 \geq m$ so that first the pies in positions $a_l$ and $b_l$ will be swapped, then the pies in positions $a_{l + 1}$ and $b_{l + 1}$ will be swapped, etc. until finally the pies in positions $a_r$ and $b_r$ are swapped.

Help Omkar choose a segment of elves such that the amount of positions in Omkar's final arrangement that contain the same type of pie as in his ideal arrangement is the maximum possible. Note that since Omkar has a big imagination, it might be that the amounts of each type of pie in his original arrangement and in his ideal arrangement do not match.

奥马尔有一个装有 $k$（$2 \leq k \leq 20$）个位置的派盘。盘中每个位置上放着一块巧克力派或南瓜派。然而，奥马尔不喜欢当前派的排列方式，他心中另有理想的排列。

为了协助奥马尔，$n$ 位精灵排成一列，准备帮他交换派盘中的派。从左往右数第 $j$ 位精灵能够交换派盘中位置 $a_j$ 和 $b_j$ 上的两块派。

为尽可能接近理想排列，奥马尔可选择一段连续的精灵子序列，并让他的派盘从左至右依次经过该子序列中的每位精灵进行交换。但由于精灵们已费心排成一列，他们要求奥马尔所选子序列长度至少为 $m$（$1 \leq m \leq n$）。

形式化地说，奥马尔需选择两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$ 且 $r - l + 1 \geq m$；然后，先交换位置 $a_l$ 和 $b_l$ 上的派，再交换位置 $a_{l+1}$ 和 $b_{l+1}$ 上的派，……，最后交换位置 $a_r$ 和 $b_r$ 上的派。

请帮助奥马尔选择一段精灵子序列，使得最终排列中与理想排列类型相同的位置数量达到最大。注意：由于奥马尔想象力丰富，其原始排列与理想排列中各类派的数量可能并不相等。

The first line contains three integers $n$, $m$, and $k$ ($1 \leq m \leq n \leq 10^6$ and $2 \leq k \leq 20$) — the number of elves, the minimum subsegment length, and the number of spots in Omkar's tray respectively.

The second and third lines each contain a string of length $k$ consisting of $0$s and $1$s that represent initial arrangement of pies and ideal arrangement of pies; the $j$-th character in each string is equal to $0$ if the $j$-th spot in the arrangement contains a chocolate pie and is equal to $1$ if the $j$-th spot in the arrangement contains a pumpkin pie. It is not guaranteed that the two strings have the same amount of $0$s or the same amount of $1$s.

$n$ lines follow. The $j$-th of these lines contains two integers $a_j$ and $b_j$ ($1 \leq a_j, b_j \leq k$, $a_j \neq b_j$) which indicate that the $j$-th elf from the left can swap the pies at positions $a_j$ and $b_j$ in the tray.

第一行包含三个整数 $n$、$m$ 和 $k$（满足 $1 \leq m \leq n \leq 10^6$ 且 $2 \leq k \leq 20$），分别表示精灵的数量、子段的最小长度，以及 Omkar 托盘上的位置数量。

第二行和第三行各包含一个长度为 $k$ 的字符串，仅由字符 $0$ 和 $1$ 组成，分别表示派的初始排列与理想排列；每个字符串中第 $j$ 个字符为 $0$ 表示该排列中第 $j$ 个位置放的是巧克力派，为 $1$ 表示放的是南瓜派。注意：两个字符串中 $0$ 的个数或 $1$ 的个数不一定相等。

接下来是 $n$ 行。其中第 $j$ 行包含两个整数 $a_j$ 和 $b_j$（满足 $1 \leq a_j, b_j \leq k$ 且 $a_j \neq b_j$），表示从左往右数第 $j$ 个精灵可以交换托盘上位置 $a_j$ 与 $b_j$ 处的派。

Output two lines.

The first line should contain a single integer $s$ ($0 \leq s \leq k$) equal to the amount of positions that contain the same type of pie in Omkar's final arrangement and in Omkar's ideal arrangement; $s$ should be the maximum possible.

The second line should contain two integers $l$ and $r$ satisfying $1 \leq l \leq r \leq n$ and $r - l + 1 \geq m$, indicating that Omkar should pass his tray through the subsegment $l, l + 1, \dots, r$ to achieve a final arrangement with $s$ positions having the same type of pie as his ideal arrangement.

If there are multiple answers you may output any of them.

输出两行。

第一行应包含一个整数 $s$（$0 \leq s \leq k$），表示 Omkar 的最终排列与理想排列中类型相同的派的位置数量；$s$ 应取可能的最大值。

第二行应包含两个整数 $l$ 和 $r$，满足 $1 \leq l \leq r \leq n$ 且 $r - l + 1 \geq m$，表明 Omkar 应将其托盘经过子段 $l, l + 1, \dots, r$，以得到一个最终排列，使其恰好有 $s$ 个位置的派类型与其理想排列一致。

若存在多个答案，输出任意一个即可。

In the first test case, the swaps will go like this:

• Swap $1$ and $3$: 11000 becomes 01100
• Swap $3$ and $5$: 01100 becomes 01001
• Swap $4$ and $2$: 01001 becomes 00011

The final arrangement is the same as the ideal arrangement 00011, so there are $5$ positions with the same type of pie, which is optimal.

In the second test case, the swaps will go like this:

• Swap $1$ and $3$: 11000 becomes 01100
• Swap $1$ and $5$: 01100 becomes 01100
• Swap $4$ and $2$: 01100 becomes 00110
• Swap $1$ and $5$: 00110 becomes 00110

The final arrangement has $3$ positions with the same type of pie as the ideal arrangement 00011, those being positions $1$, $2$, and $4$. In this case the subsegment of elves $(l, r) = (2, 3)$ is more optimal, but that subsegment is only length $2$ and therefore does not satisfy the constraint that the subsegment be of length at least $m = 3$.

在第一个测试用例中，交换过程如下：

• 交换位置 $1$ 和 $3$：11000 变为 01100
• 交换位置 $3$ 和 $5$：01100 变为 01001
• 交换位置 $4$ 和 $2$：01001 变为 00011

最终排列与理想排列 00011 相同，因此有 $5$ 个位置上的派种类与理想排列一致，这是最优结果。

在第二个测试用例中，交换过程如下：

• 交换位置 $1$ 和 $3$：11000 变为 01100
• 交换位置 $1$ 和 $5$：01100 变为 01100
• 交换位置 $4$ 和 $2$：01100 变为 00110
• 交换位置 $1$ 和 $5$：00110 变为 00110

最终排列中，有 $3$ 个位置上的派种类与理想排列 00011 一致，这些位置是第 $1$、$2$ 和 $4$ 位。此时子段 $(l, r) = (2, 3)$ 的精灵更优，但该子段长度仅为 $2$，不满足子段长度至少为 $m = 3$ 的约束条件。