题目背景

这个题本来是要拿到 Tree Diagram 上算的，但是 Tree Diagram 被某组织的宇宙射线射爆了，所以这个问题交给了你。

不过你不需要计算出可能出现的最坏情况，只需要解决原问题就可以了。

题目描述

给你一个长度为 $n$ 的序列 $a$，求其所有子区间的按位或和的和。

输入格式

本题采用特殊的读入方式。以下是读入模板：

#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);
}

初始调用一次 READ::init(n)，之后你应调用 $n$ 次 READ::read()，第 $i$ 次 READ::read 返回 $a_i$。

输出格式

一个整数，表示答案。答案对 $2^{64}$ 取模。

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

544

提示

保证读入模板消耗的时间少于 200ms，空间少于 1MB。

数据规模

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n\le 5\times 10^7$，$0\le a_i <2^{64}$。