Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/white-falcon-and-tree/problem?isFullScreen=true
In this HackerRank in Data Structures -
White Falcon has a tree with N nodes. Each node contains a linear function. Let's denote by fu(x) the linear function contained in the node
.
Let's denote the path from node u to node v like this: p1,p2,p3, ... , pk where p1 = u and pk = v and pi and p(i+1) are connected. White Falcon also has Q queries. They are in the following format:
- 1 u v ab. Assign ax + b as the function of all the nodes on the path from u to v i.e., f pi (x) is changed to ax + b where p1,p2,p3, ... , pk is the path from u to v.
- 2 u v x . Calculate f pk (f p(k-1)(f p(k-2)(.... fp1 (x)))) modulo (10**9 + 7)
Input Format
The first line contains N,the number of nodes. The following N lines each contain two integers a and b that describe the function ax + b
Following N - 1 lines contain edges of the tree.
The next line contains Q, the number of queries. Each subsequent line contains one of the queries described above.
Output Format
For every query of the second kind, print one line containing an integer, the answer for that query.
Constraints
1 <= N <= 50000 (Number of nodes)
1 <= Q <= 50000 (Number of nodes)
0 <= a,b,x <= 10**9 +7
Sample Input
2
1 1
1 2
1 2
2
1 2 2 1 1
2 1 2 1
Sample Output
3
Explanation
f1(1) = 2
f2(2) = 3
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
typedef struct _tree{
long long sum[2][2];
long long sum1[2][2];
long long offset1;
long long offset2;
} tree;
#define MOD 1000000007
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void preprocess();
int lca(int a,int b);
void sum(int v,int tl,int tr,int l,int r,tree *t,long long ans[][2],int f);
void range_update(int v,int tl,int tr,int pos1,int pos2,long long o1,long long o2,tree *t);
void merge(long long a[][2],long long b[][2],long long ans[][2]);
void push(int v,int tl,int tr,tree *t);
void range_solve(int x,int y,int a,int b);
int min(int x,int y);
int max(int x,int y);
long long solve(int x,int y,int a);
void one(long long*a,int SIZE);
void mul(long long*a,long long*b,int SIZE);
void powm(long long*a,int n,long long*res,int SIZE);
int N,cn,A[100000],B[100000],level[100000],DP[18][100000],subtree_size[100000],special[100000],node_chain[100000],node_idx[100000],chain_head[100000],chain_len[100000]={0};
lnode *table[100000]={0};
tree *chain[100000];
int main(){
int Q,x,y,a,b,i;
scanf("%d",&N);
for(i = 0; i < N; i++)
scanf("%d%d",A+i,B+i);
for(i = 0; i < N-1; i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
preprocess();
scanf("%d",&Q);
while(Q--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d%d%d",&x,&y,&a,&b);
range_solve(x-1,y-1,a,b);
break;
default:
scanf("%d%d%d",&x,&y,&a);
printf("%lld\n",solve(x-1,y-1,a));
}
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int u){
lnode *x;
subtree_size[u]=1;
special[u]=-1;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
subtree_size[u]+=subtree_size[x->x];
if(special[u]==-1 || subtree_size[x->x]>subtree_size[special[u]])
special[u]=x->x;
}
return;
}
void dfs1(int u,int c){
lnode *x;
node_chain[u]=c;
node_idx[u]=chain_len[c]++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
if(x->x==special[u])
dfs1(x->x,c);
else{
chain_head[cn]=x->x;
dfs1(x->x,cn++);
}
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i = 1; i < 18; i++)
for(j = 0; j < N; j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
cn=1;
chain_head[0]=0;
dfs1(0,0);
for(i = 0; i < cn; i++){
chain[i]=(tree*)malloc(4*chain_len[i]*sizeof(tree));
memset(chain[i],0,4*chain_len[i]*sizeof(tree));
for(j = 0; j < 4*chain_len[i]; j++)
chain[i][j].offset1=chain[i][j].offset2=-1;
}
for(i = 0; i < N; i++)
range_update(1,0,chain_len[node_chain[i]]-1,node_idx[i],node_idx[i],A[i],B[i],chain[node_chain[i]]);
return;
}
int lca(int a,int b>{
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i = 0; i < 18; i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b>return a;
for(i=17;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
void sum(int v,int tl,int tr,int l,int r,tree *t,long long ans[][2],int f){
long long a[2][2],b[2][2];
push(v,tl,tr,t);
if(l>r){
ans[0][0]=1;
ans[0][1]=0;
ans[1][0]=0;
ans[1][1]=1;
return;
}
if(l==tl && r==tr){
if(f)
memcpy(ans,t[v].sum1,sizeof(t[v].sum1));
else
memcpy(ans,t[v].sum,sizeof(t[v].sum));
return;
}
int tm=(tl+tr)/2;
sum(v*2,tl,tm,l,min(r,tm),t,a,f);
sum(v*2+1,tm+1,tr,max(l,tm+1),r,t,b,f);
if(f)
merge(b,a,ans);
else
merge(a,b,ans);
return;
}
void range_update(int v,int tl,int tr,int pos1,int pos2,long long o1,long long o2,tree *t){
push(v,tl,tr,t);
if(pos2 < tl || pos1>tr)
return;
int tm=(tl+tr)/2;
if(pos1 < =tl && pos2>=tr){
t[v].offset1=o1;
t[v].offset2=o2;
}
else{
range_update(v*2,tl,tm,pos1,pos2,o1,o2,t);
range_update(v*2+1,tm+1,tr,pos1,pos2,o1,o2,t);
push(v*2,tl,tm,t);
push(v*2+1,tm+1,tr,t);
merge(t[v*2].sum,t[v*2+1].sum,t[v].sum);
merge(t[v*2+1].sum1,t[v*2].sum1,t[v].sum1);
}
return;
}
void merge(long long a[][2],long long b[][2],long long ans[][2]){
ans[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
ans[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
ans[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
ans[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
return;
}
void push(int v,int tl,int tr,tree *t){
long long a[2][2];
if(t[v].offset1==-1 || t[v].offset2==-1)
return;
a[0][0]=t[v].offset1;
a[0][1]=t[v].offset2;
a[1][0]=0;
a[1][1]=1;
powm(&a[0][0],tr-tl+1,&t[v].sum[0][0],2);
memcpy(t[v].sum1,t[v].sum,sizeof(t[v].sum));
if(tl!=tr){
t[v*2].offset1=t[v*2+1].offset1=t[v].offset1;
t[v*2].offset2=t[v*2+1].offset2=t[v].offset2;
}
t[v].offset1=t[v].offset2=-1;
return;
}
void range_solve(int x,int y,int a,int b){
int ca=lca(x,y);
while(node_chain[x]!=node_chain[ca]){
range_update(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],a,b,chain[node_chain[x]]);
x=DP[0][chain_head[node_chain[x]]];
}
range_update(1,0,chain_len[node_chain[x]]-1,node_idx[ca],node_idx[x],a,b,chain[node_chain[x]]);
while(node_chain[y]!=node_chain[ca]){
range_update(1,0,chain_len[node_chain[y]]-1,0,node_idx[y],a,b,chain[node_chain[y]]);
y=DP[0][chain_head[node_chain[y]]];
}
if(node_idx[y]!=node_idx[ca])
range_update(1,0,chain_len[node_chain[y]]-1,node_idx[ca]+1,node_idx[y],a,b,chain[node_chain[y]]);
return;
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y>{
return (x>y)?x:y;
}
long long solve(int x,int y,int a){
int ca=lca(x,y);
long long t1[2][2],t2[2][2]={1,0,0,1},t3[2][2],ans[2][2];
while(node_chain[x]!=node_chain[ca]){
sum(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],chain[node_chain[x]],t1,0);
memcpy(t3,t2,sizeof(t2));
merge(t1,t3,t2);
x=DP[0][chain_head[node_chain[x]]];
}
sum(1,0,chain_len[node_chain[x]]-1,node_idx[ca],node_idx[x],chain[node_chain[x]],t1,0);
memcpy(t3,t2,sizeof(t2));
merge(t1,t3,ans);
t2[0][0]=1;
t2[0][1]=0;
t2[1][0]=0;
t2[1][1]=1;
while(node_chain[y]!=node_chain[ca]){
sum(1,0,chain_len[node_chain[y]]-1,0,node_idx[y],chain[node_chain[y]],t1,1);
memcpy(t3,t2,sizeof(t2));
merge(t3,t1,t2);
y=DP[0][chain_head[node_chain[y]]];
}
if(node_idx[y]!=node_idx[ca]){
sum(1,0,chain_len[node_chain[y]]-1,node_idx[ca]+1,node_idx[y],chain[node_chain[y]],t1,1);
memcpy(t3,t2,sizeof(t2));
merge(t3,t1,t2);
}
merge(t2,ans,t1);
return (a*t1[0][0]+t1[0][1])%MOD;
}
void one(long long*a,int SIZE){
int i,j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i*SIZE+j] = (i == j);
return;
}
void mul(long long*a,long long*b,int SIZE){
int i,j,k;
long long res[SIZE][SIZE];
for(i=0;i < SIZE;i++)
for(j=0;j < SIZE;j++)
res[i][j]=0;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
for (k = 0; k < SIZE; k++)
res[i][j] = (res[i][j]+a[i*SIZE+k] * b[k*SIZE+j])%MOD;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i*SIZE+j] = res[i][j];
return;
}
void powm(long long*a,int n,long long*res,int SIZE){
one(res,SIZE>;
while (n > 0) {
if (n % 2 == 0)
{
mul(a, a,SIZE);
n /= 2;
}
else {
mul(res, a,SIZE);
n--;
}
}
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define N 50005
int a[N], b[N], sz[N], top[N], ch[N], f[N], st[N], w[N], p[N][18], d[N], cnt, n;
vi g[N];
void dfs(int u, int fa){
sz[u] = 1;
for(int i = 0; i < g[u].size(); i++){
int j = g[u][i];
if(j == fa) continue;
dfs(j, u);
sz[u] += sz[j];
if(ch[u] == 0 || sz[ch[u]] < sz[j]) ch[u]=j;
}
}
void go(int u, int fa, int p){
st[u] = ++cnt; w[cnt] = u; top[u] = p; f[u] = fa; d[u] = d[fa] + 1;
if(ch[u] == 0) {return;}
go(ch[u], u, p);
for(int i = 0; i < g[u].size(); i++){
int j = g[u][i];
if(j == fa || j == ch[u]) continue;
go(j, u, j);
}
}
int lca(int a, int b){
if(d[a] < d[b]) swap(a, b>;
int h = d[a] - d[b];
for(int i = 17; i >= 0; i--)
if(h >> i & 1) a = p[a][i];
if(a == b) return a;
for(int i = 17; i >= 0; i--)
if(p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
return p[a][0];
}
int pow(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = 1LL * ans * a % mod;
b >>= 1; a = 1LL * a * a % mod;
}
return ans;
}
struct node{
int a, b1, b2, ca, cb;
} t[N << 2];
void up(int p){
t[p].a = 1LL * t[p << 1].a * t[p << 1 | 1].a % mod;
t[p].b1 = (1LL * t[p << 1].a * t[p << 1 | 1].b1 % mod + t[p << 1].b1) % mod;
t[p].b2 = (1LL * t[p << 1 | 1].a * t[p << 1].b2 % mod + t[p << 1 | 1].b2) % mod;
}
void build(int p, int l, int r){
t[p].ca = t[p].cb = -1;
if(l == r){
t[p].a = a[w[l]];
t[p].b1 = t[p].b2 = b[w[l]];
return;
}
int m = (l + r) >> 1;
build(p << 1, l, m);
build(p << 1 | 1, m + 1, r);
up(p);
}
void cal(int p, int l, int r, int a, int b){
t[p].a = pow(a, r - l + 1);
if(a == 1){
int v = 1LL * b * (r - l + 1) % mod;
t[p].b1 = t[p].b2 = v;
}
else{
int v = t[p].a - 1;
if(v < 0) v += mod;
int w = a - 1;
if(w < 0) w += mod;
w = pow(w, mod - 2);
v = 1LL * v * w % mod * b % mod;
t[p].b1 = t[p].b2 = v;
}
t[p].ca = a, t[p].cb = b;
}
void down(int p, int l, int r){
if(t[p].ca != -1){
int m = (l + r) >> 1;
cal(p << 1, l, m, t[p].ca, t[p].cb);
cal(p << 1 | 1, m + 1, r, t[p].ca, t[p].cb);
t[p].ca = -1;
}
}
void upd(int p, int l, int r, int x, int y, int a, int b>{
if(l >= x && r <= y){
cal(p, l, r, a, b);
return;
}
int m = (l + r) >> 1;
down(p, l, r);
if(x < = m) upd(p << 1, l, m, x, y, a, b>;
if(y > m) upd(p << 1 | 1, m + 1, r, x, y, a, b);
up(p);
}
void query(int p, int l, int r, int x, int y, int &a, int &b, int k){
if(l >= x && r <= y){
a = t[p].a;
if(k) b = t[p].b1;
else b = t[p].b2;
return;
}
a = 1; b = 0;
int m = (l + r) >> 1, a1 = 1, b1 = 0, a2 = 1, b2 = 0;
down(p, l, r);
if(x < = m) query(p << 1, l, m, x, y, a1, b1, k>;
if(y > m) query(p << 1 | 1, m + 1, r, x, y, a2, b2, k);
a = 1LL * a2 * a1 % mod;
if(k) b = (1LL * a1 * b2 % mod + b1) % mod;
else b = (1LL * a2 * b1 % mod + b2) % mod;
up(p);
}
void change(int u, int v, int a, int b){
while(top[u] != top[v]){
int x = top[u];
upd(1, 1, n, st[x], st[u], a, b);
u = f[x];
}
upd(1, 1, n, st[v], st[u], a, b);
}
void query(int u, int v, int &a, int &b, int dir){
a = 1, b = 0;
while(top[u] != top[v]){
int x = top[u], a1, b1;
query(1, 1, n, st[x], st[u], a1, b1, dir);
if(dir == 0) b = (1LL * a * b1 % mod + b) % mod;
else b = (1LL * a1 * b % mod + b1) % mod;
a = 1LL * a * a1 % mod;
u = f[x];
}
int a1, b1;
query(1, 1, n, st[v], st[u], a1, b1, dir);
if(dir == 0) b = (1LL * a * b1 % mod + b) % mod;
else b = (1LL * a1 * b % mod + b1) % mod;
a = 1LL * a * a1 % mod;
}
int main(){
int T, i, j, ca = 0, k, m;
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
for(i = 1; i < n; i++){
scanf("%d%d", &j, &k);
g[j].pb(k); g[k].pb(j);
}
dfs(1, 0); cnt = 0;
go(1, 0, 1);
p[1][0] = 1;
for(i = 1; i < = n; i++) p[i][0] = f[i];
for(i = 1; i < 18; i++)
for(j = 1; j < = n; j++)
p[j][i] = p[p[j][i - 1]][i - 1];
build(1, 1, n);
scanf("%d", &m);
while(m--){
int x, y;
scanf("%d%d%d", &k, &x, &y);
if(k == 1){
int a, b; scanf("%d%d", &a, &b);
int fa = lca(x, y);
if(x == fa) change(y, x, a, b);
else if(y == fa) change(x, y, a, b>;
else{
int h = d[x] - d[fa] - 1;
int u = x;
for(i = 17; i >= 0; i--)
if(h >> i & 1) u = p[u][i];
change(x, u, a, b); change(y, fa, a, b);
}
}
else {
int v; scanf("%d", &v);
int fa = lca(x, y), a, b;
if(x == fa) query(y, x, a, b, 0);
else if(y == fa) query(x, y, a, b, 1);
else{
int h = d[x] - d[fa] - 1;
int u = x, a1, b1;
for(i = 17; i >= 0; i--)
if(h >> i & 1) u = p[u][i];
query(x, u, a, b, 1); query(y, fa, a1, b1, 0);
b = (1LL * a1 * b % mod + b1) % mod; a = 1LL * a * a1 % mod;
}
printf("%d\n", (1LL * a * v % mod + b) % mod);
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static int mod = 1000000007;
static void solve()
{
int n = ni();
int[][] co = new int[n][];
for(int i = 0;i < n;i++){
co[i] = new int[]{ni(), ni()};
}
int[] from = new int[n-1];
int[] to = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
int[] clus = decomposeToHeavyLight(g, par, ord);
int[][] cluspath = clusPaths(clus, ord);
int[] clusiind = clusIInd(cluspath, n);
SegmentTreeNodePlus[] sts = new SegmentTreeNodePlus[cluspath.length];
for(int i = 0;i < cluspath.length;i++){
int[][] lco = new int[cluspath[i].length][];
for(int j = 0;j < cluspath[i].length;j++){
lco[j] = co[cluspath[i][j]];
}
sts[i] = new SegmentTreeNodePlus(lco);
}
int[][] spar = logstepParents(par);
int Q = ni();
for(int z = 0;z < Q;z++){
int t = ni();
if(t == 1){
int u = ni()-1, v = ni()-1, a = ni(), b = ni();
int lca = lca2(u, v, spar, dep);
int[][] pr = query2(u, lca, v, clus, cluspath, clusiind, par);
for(int[] e : pr){
sts[e[0]].update(Math.min(e[1], e[2]), Math.max(e[1], e[2])+1, a, b);
}
}else{
int u = ni()-1, v = ni()-1;
long x = ni();
int lca = lca2(u, v, spar, dep);
int[][] pr = query2(u, lca, v, clus, cluspath, clusiind, par);
for(int[] e : pr){
if(e[1] <= e[2]){
x = sts[e[0]].apply(e[1], e[2]+1, x, false);
}else{
x = sts[e[0]].apply(e[2], e[1]+1, x, true);
}
}
out.println(x);
}
}
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar>;
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1
: pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static class SegmentTreeNodePlus {
public int M, H, N;
public Node[] node;
public int[][] cover;
private static class Node
{
long co;
long lc;
long rc;
public Node() {
co = 1;
lc = rc = 0;
}
public Node(long co, long lc, long rc) {
this.co = co;
this.lc = lc;
this.rc = rc;
}
public long apply(long x, boolean dir)
{
if(!dir){
return (co * x + lc) % mod;
}else{
return (co * x + rc) % mod;
}
}
}
public SegmentTreeNodePlus(int[][] co)
{
N = co.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
node = new Node[M];
cover = new int[H][];
for(int i = 0;i < N;i++){
node[H+i] = new Node(co[i][0], co[i][1], co[i][1]>;
}
for(int i = H-1;i >= 1;i--)propagate(i);
}
private void propagate(int cur)
{
node[cur] = prop2(node[2*cur], node[2*cur+1], cover[cur], node[cur], H/Integer.highestOneBit(cur));
}
static final int mod = 1000000007;
private Node prop2(Node L, Node R, int[] cover, Node C, int len)
{
if(L != null && R != null){
if(C == null)C = new Node();
if(cover == null){
C.co = L.co * R.co % mod;
C.lc = (R.co * L.lc + R.lc) % mod;
C.rc = (L.co * R.rc + L.rc) % mod;
}else{
long co = cover[0], c = cover[1];
for(int x = len;x > 1;x >>>= 1){
long nco = co * co % mod;
long nc = (co * c + c) % mod;
co = nco;
c = nc;
}
C.co = co;
C.lc = C.rc = c;
}
return C;
}else if(L != null){
return prop1(L, cover, C, len);
}else if(R != null){
return prop1(R, cover, C, len);
}else{
return null;
}
}
private Node prop1(Node L, int[] cover, Node C, int len)
{
if(C == null)C = new Node();
if(cover == null){
C.co = L.co;
C.lc = L.lc;
C.rc = L.rc;
}else{
long co = cover[0], c = cover[1];
for(int x = len;x > 1;x >>>= 1){
long nco = co * co % mod;
long nc = (co * c + c) % mod;
co = nco;
c = nc;
}
C.co = co;
C.lc = C.rc = c;
}
return C;
}
int[] temp = null;
public void update(int l, int r, int a, int b) {
temp = new int[]{a, b};
if(l < r)update(l, r, a, b, 0, H, 1); }
protected void update(int l, int r, int a, int b, int cl, int cr, int cur>
{
if(cur >= H){
node[cur].co = a;
node[cur].lc = node[cur].rc = b;
}else if(l <= cl && cr < = r){
cover[cur] = temp;
propagate(cur>;
}else{
int mid = cl+cr>>>1;
boolean bp = false;
if(cover[cur] != null){
if(2*cur < H){
cover[2*cur] = cover[cur];
cover[2*cur+1] = cover[cur];
cover[cur] = null;
bp = true;
}else{
node[2*cur].co = cover[cur][0];
node[2*cur].lc = node[2*cur].rc = cover[cur][1];
node[2*cur+1].co = cover[cur][0];
node[2*cur+1].lc = node[2*cur+1].rc = cover[cur][1];
cover[cur] = null;
}
}
if(cl < r && l < mid){
update(l, r, a, b, cl, mid, 2*cur);
}else if(bp){
propagate(2*cur);
}
if(mid < r && l < cr){
update(l, r, a, b, mid, cr, 2*cur+1);
}else if(bp){
propagate(2*cur+1);
}
propagate(cur);
}
}
public long apply(int l, int r, long x, boolean dir) {
return apply(l, r, x, dir, 0, H, 1);
}
protected long apply(int l, int r, long x, boolean dir, int cl, int cr, int cur)
{
if(l < = cl && cr <= r){
return node[cur].apply(x, dir>;
}else{
int mid = cl+cr>>>1;
if(cover[cur] != null){
long co = cover[cur][0], c = cover[cur][1];
for(int h = Math.min(r, cr) - Math.max(l, cl);h > 0;h >>>= 1){
if((h&1) == 1){
x = (co * x + c) % mod;
}
long nco = co * co % mod;
long nc = (co * c + c) % mod;
co = nco;
c = nc;
}
return x;
}
if(!dir){
if(cl < r && l < mid){
x = apply(l, r, x, dir, cl, mid, 2*cur);
}
if(mid < r && l < cr){
x = apply(l, r, x, dir, mid, cr, 2*cur+1);
}
}else{
if(mid < r && l < cr){
x = apply(l, r, x, dir, mid, cr, 2*cur+1);
}
if(cl < r && l < mid){
x = apply(l, r, x, dir, cl, mid, 2*cur);
}
}
return x;
}
}
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
public static int[] decomposeToHeavyLight(int[][] g, int[] par, int[] ord)
{
int n = g.length;
int[] size = new int[n];
Arrays.fill(size, 1>;
for(int i = n-1;i > 0;i--)size[par[ord[i]]] += size[ord[i]];
int[] clus = new int[n];
Arrays.fill(clus, -1);
int p = 0;
outer:
for(int i = 0;i < n;i++){
int u = ord[i];
if(clus[u] == -1)clus[u] = p++;
for(int v : g[u]){
if(par[u] != v && size[v] >= size[u]/2){
clus[v] = clus[u];
continue outer;
}
}
for(int v : g[u]){
if(par[u] != v){
clus[v] = clus[u];
break;
}
}
}
return clus;
}
public static int[][] clusPaths(int[] clus, int[] ord)
{
int n = clus.length;
int[] rp = new int[n];
int sup = 0;
for(int i = 0;i < n;i++){
rp[clus[i]]++;
sup = Math.max(sup, clus[i]);
}
sup++;
int[][] row = new int[sup][];
for(int i = 0;i < sup;i++>row[i] = new int[rp[i]];
for(int i = n-1;i >= 0;i--){
row[clus[ord[i]]][--rp[clus[ord[i]]]] = ord[i];
}
return row;
}
public static int[] clusIInd(int[][] clusPath, int n)
{
int[] iind = new int[n];
for(int[] path : clusPath){
for(int i = 0;i < path.length;i++){
iind[path[i]] = i;
}
}
return iind;
}
public static int[][] query2(int x, int anc, int y, int[] clus, int[][] cluspath, int[] clusiind, int[] par)
{
int[][] stack = new int[60][];
int sp = 0;
int cx = clus[x];
int indx = clusiind[x];
while(cx != clus[anc]){
stack[sp++] = new int[]{cx, indx, 0};
int con = par[cluspath[cx][0]];
indx = clusiind[con];
cx = clus[con];
}
stack[sp++] = new int[]{cx, indx, clusiind[anc]};
int top = sp;
int cy = clus[y];
int indy = clusiind[y];
while(cy != clus[anc]){
stack[sp++] = new int[]{cy, 0, indy};
int con = par[cluspath[cy][0]];
indy = clusiind[con];
cy = clus[con];
}
if(clusiind[anc] < indy){
stack[sp++] = new int[]{cy, clusiind[anc]+1, indy};
}
for(int p = top, q = sp-1;p < q;p++,q--){
int[] dum = stack[p]; stack[p] = stack[q]; stack[q] = dum;
}
return Arrays.copyOf(stack, sp);
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static void main(String[] args) throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException(>;
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c> { return !(c >= 33 && c < = 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b < = '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()> != -1 && !((b >= '0' && b < = '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte(>;
}
}
}