J. F Less Than G
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Khaled is a bad boy, and he loves to rip papers. His father has got tired of him, and he wants to go on a trip with his friends, and your job is to take care of him.

Bad boy Khaled usually comes up with bad problems and wants people to solve them, and if they don't, he gets mad and starts ripping a lot of papers. He gives you this problem and wants you to solve it.

Given two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ non-negative integers, count the number of good pairs $$$l$$$,$$$r$$$ $$$(1 \le l \le r \le n)$$$, satisfying $$$$$$F(l,r) \lt G(l,r)$$$$$$ Where $$$F(l,r)$$$ is the sum of the square of numbers in the range $$$[l,r]$$$ from the array $$$a$$$, more formally: $$$$$$F(l,r) = {\sum_{i = l}^r a_i^2}$$$$$$

And $$$G(l,r)$$$ is the square of the bitwise OR of the range $$$[l,r]$$$ from the array $$$b$$$, more formally:

$$$$$$ G(l,r) = (b_l | b_{l+1} | .... b_r)^2 $$$$$$

Where | is the bitwise OR operation. To prevent Khaled from ripping your papers, you have to solve his problem.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2*10^5)$$$, the length of the arrays $$$a$$$ and $$$b$$$.

The second line contains $$$n$$$ non-negative integers $$$a_1,....,a_n$$$ $$$(0 \le a_i \le 10^6)$$$.

The third line contains $$$n$$$ non-negative integers $$$b_1,....,b_n$$$ $$$(0 \le b_i \le 10^6)$$$.

Output

Output the number of good pairs

Examples
Input
1
2
3
Output
1
Input
2
1 6
3 4
Output
2
Input
5
1 2 4 3 1
1 4 8 7 1
Output
13