Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Xor-Set

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given two sets of integers: $$$A$$$ and $$$B$$$. You need to output the sum of elements in the set $$$C = \{x | x = a \oplus b, a \in A, b \in B\}$$$ modulo $$$998244353$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. Each number should be counted only once.

For example, if $$$A = \{2, 3\}$$$ and $$$B = \{2, 3\}$$$ you should count integer $$$1$$$ only once, despite the fact that you can get it as $$$3 \oplus 2$$$ and as $$$2 \oplus 3$$$. So the answer for this case is equal to $$$1 + 0 = 1$$$.

Let's call a segment $$$[l; r]$$$ a set of integers $$$\{l, l+1, \dots, r\}$$$.

The set $$$A$$$ is given as a union of $$$n_A$$$ segments, the set $$$B$$$ is given as a union of $$$n_B$$$ segments.

Input

The first line contains a single integer $$$n_A$$$ ($$$1 \le n_A \le 100$$$).

The $$$i$$$-th of the next $$$n_A$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$), describing a segment of values of set $$$A$$$.

The next line contains a single integer $$$n_B$$$ ($$$1 \le n_B \le 100$$$).

The $$$i$$$-th of the next $$$n_B$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le 10^{18}$$$), describing a segment of values of set $$$B$$$.

Note that segments in both sets may intersect.

Output

Print one integer — the sum of all elements in set $$$C = \{x | x = a \oplus b, a \in A, b \in B\}$$$ modulo $$$998244353$$$.

Examples

Input

2 3 5 5 8 3 1 2 1 9 2 9

Output

112

Input

1 1 9 2 2 4 2 10

Output

120

Note

In the second example, we can discover that the set $$$C = \{0,1,\dots,15\}$$$, which means that all numbers between $$$0$$$ and $$$15$$$ can be represented as $$$a \oplus b$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/05/2020 08:20:03 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|