Matrix<modint>x(2,2);
ll@k,@n;
modint().setmod(k);
segtree_Point_Prod<Matrix<modint>>t;
t.malloc(n);
t.setN(n,0,0);
rep(i,n){
	rd(x(2,2));
	t[i]=x;
}
t.build();
ll@q;
rep(q){
	ll@i--,@l--,@r;
	rd(x(2,2));
	t.change(i,x);
	x=t.getProd(l,r);
	wt(x(2,2));
}