Background

This problem was originally meant to be solved on a Tree Diagram, but the Tree Diagram was blasted by some organization’s cosmic rays, so the problem is now handed to you.

However, you do not need to compute the worst-case scenario that could occur. You only need to solve the original problem.

Problem Description

You are given a sequence $a$ of length $n$. Find the sum of the bitwise OR sums over all subintervals.

Input Format

This problem uses a special input method. Below is the input template:

#include<bits/stdc++.h>
#define Misaka namespace  
#define Mikoto std 
#define ull unsigned long long 
using Misaka Mikoto;
namespace READ
{
	ull Read()
	{
		char ch=getchar();
		ull s=0;
		while(ch<'0'||ch>'9') ch=getchar();
		while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
		return s;
	}
	ull tp[10005];
	int l,r;
	ull g1,g2;
	void init(int &n)
	{
		int i,k;
		n=Read(),k=Read(),l=1;
		for(i=1;i<=k;i++)
			tp[i]=Read();
	}
	ull read()
	{
		if(l>r)
			l=Read(),r=Read(),g1=Read(),g2=Read();
		return tp[l++]*g1+g2;
	}
}
int main()
{
	int n;
   	READ::init(n);
}

Call READ::init(n) once at the beginning. Then you should call READ::read() exactly $n$ times. The $i$-th call to READ::read returns $a_i$.

Output Format

Output one integer, representing the answer. The answer is taken modulo $2^{64}$.

10 10
2 8 9 1 9 2 7 1 2 10
1 10 1 1

544

Hint

It is guaranteed that the input template takes less than 200 ms in time and less than 1 MB in memory.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le n\le 5\times 10^7$ and $0\le a_i <2^{64}$.

Translated by ChatGPT 5