题目描述

对于非负整数 $n$ 和 $m$，定义 $f(n,m) = \max_{0 \le i \le n,0 \le j \le m} i \oplus j$，其中 $\oplus$ 表示二进制异或。也就是说，$f(n,m)$ 表示，如果你选择一个 $\le n$ 的自然数和一个 $\le m$ 的自然数，他们的二进制异或结果最大为多少。

给定整数 $l$、$r$、$x$、$y$，请你求出 $\sum_{i=l}^r \sum_{j=x}^y f(i,j)$ 对 $998244353$ 取模的值。

由于 $l,r,x,y$ 可能很大，都以二进制的形式给出。二进制串左侧为高位，右侧为低位，比如 $(100)_2 = 4$。

注意，二进制串可能有前导 $0$。

输入格式

第一行一个正整数 $L$，表示后续四个二进制串的长度。

接下来四行，每行一个长为 $L$ 的二进制串，分别表示 $l$、$r$、$x$ 和 $y$。保证 $l \le r$ 且 $x \le y$。

输出格式

一行一个整数，表示所求的值。

输入样例 #1

3
000
010
000
010

输出样例 #1

16

输入样例 #2

12
000000101010
111111111111
000000000111
111111101111

输出样例 #2

374883400

说明提示

对于所有的数据，$1 \le L \le 5 \times 10^5$。

本站补充：原套别：第 13 套 B 题。