1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| #include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
template<typename Ty> void read(Ty &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,m;
int O[maxn*50],head1;
struct oy {
ll x;int y,z;
void add(int id,ll tmp1,int tmp2) {
z=O[id],x=tmp1,y=tmp2;O[id]=head1;
}
}o1[maxn*80];
int to[maxn*50],head2;
struct ty {
ll x;int y,z;
void add(int id,ll tmp1,int tmp2) {
z=to[id],x=tmp1,y=tmp2;to[id]=head2;
}
}o2[maxn*50];
const int base=61;
namespace tr {
int a[maxn*50][3],root=1,cnt=1;
void insert(ll x,int w,int len) {
int now=root,i;
for (i=0;i<=len;i++) {
int tmp=(x>>i)&1;
if (!a[now][tmp]) a[now][tmp]=++cnt;
now=a[now][tmp];
}
if (!a[now][0]) a[now][0]=++cnt;
if (!a[now][1]) a[now][1]=++cnt;
a[a[now][0]][2]+=w,a[a[now][1]][2]+=w;
}
int query(ll x,int len) {
int now=root,sum=0,i;
for (i=0;i<=len;i++) {
int tmp=(x>>i)&1;
sum+=a[now][2];
if (!a[now][tmp]) return sum;
now=a[now][tmp];
}
sum+=a[now][2];
return sum;
}
}
int f[maxn*50][2],Ans[maxn];
int root=1,cnt=1;
void insert(ll x,ll y,int w,int id,int len) {
int now=root,i;
for (i=0;i<=len;i++) {
int tmp=(x>>i)&1;
if (!f[now][tmp]) f[now][tmp]=++cnt;
now=f[now][tmp];
}
if (!f[now][0]) f[now][0]=++cnt;
if (!f[now][1]) f[now][1]=++cnt;
if (id) o2[++head2].add(now,y,id);
else {
o1[++head1].add(f[now][0],y,w);
o1[++head1].add(f[now][1],y,w);
}
}
int calc(ll x) {
int l=0,r=61,mid;
while (l+1<r) {
int mid=l+r>>1;
if ((1ll<<mid)<=x) l=mid;
else r=mid;
}
return l;
}
void solve(int x) {
int i;pair<ll,ll>tmp;
for (i=O[x];i;i=o1[i].z) {
tmp.fi=o1[i].x,tmp.se=o1[i].y;
tr::insert(tmp.fi,tmp.se,calc(tmp.fi)-1);
}
for (i=to[x];i;i=o2[i].z) {
tmp.fi=o2[i].x,tmp.se=o2[i].y;
Ans[tmp.se]=tr::query(tmp.fi,calc(tmp.fi));
}
if (f[x][0]) solve(f[x][0]);
if (f[x][1]) solve(f[x][1]);
for (i=O[x];i;i=o1[i].z) {
tmp.fi=o1[i].x,tmp.se=o1[i].y;
tr::insert(tmp.fi,-tmp.se,calc(tmp.fi)-1);
}
}
signed main(void){
int i;
ll x,y,z;
read(n);read(m);
for (i=1;i<=n;i++) {
read(x),read(y),read(z);
insert(x,y,z,0,calc(x)-1);
}
for (i=1;i<=m;i++) {
read(x),read(y);
insert(x,y,0,i,calc(x));
}
solve(root);
for (i=1;i<=m;i++) printf("%d\n",Ans[i]);
return 0;
}
|