DDOSvoid is learning about bitwise operations and has come across an interesting problem.
You are given two sequences, ��ai and ��bi, both of length �n. Additionally, there are �m queries. In each query, you are given an interval [�,�][l,r]. Your task is to calculate the bitwise OR operation on the following integers:��,��+��+1,��+��+1+��+2,⋯,��+1+��+2,��+1+��+2+��+3,⋯,��al,al+bl+1,al+bl+1+bl+2,⋯,al+1+bl+2,al+1+bl+2+bl+3,⋯,ar. In other words, you need to evaluate ⨁�=��⨁�=��(��+∑�=�+1���)⨁i=lr⨁j=ir(ai+∑k=i+1jbk). The symbol ⊕⊕ represents the bitwise OR operation.
The first line of the input contains a single integer �T, indicating the number of test cases.
In each test case:
The first line contains to integers �,�(1≤�≤105,1≤�≤106)n,m(1≤n≤105,1≤m≤106).
The second line contains �n integers ��(0≤��≤5×108)ai(0≤ai≤5×108).
The third line contains �n integers ��(0≤��≤5000)bi(0≤bi≤5000).
The next �m lines, each line contains two integers �,�(1≤�≤�≤�)l,r(1≤l≤r≤n).
It is guaranteed that in all test cases, ∑�≤105,∑�≤106∑n≤105,∑m≤106.
To simply the output, we use ����ansi to represent the answer to the i-th query and ����=233,�=998244353base=233,P=998244353.
In each test case you just need to output an integer (∑�=1�����×�����)mod�(∑i=1mansi×basei)modP.
1
5 1
1 2 3 4 5
1 1 1 1 1
2 41631