AND Segments - VietMX's Blog

You are given three integers $n$, $k$, $m$ and $m$ conditions $(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$.

Calculate the number of distinct arrays $a$, consisting of $n$ integers such that:

$0 \le a_i < 2^k$ for each $1 \le i \le n$;
bitwise AND of numbers $a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$ for each $1 \le i \le m$.

Two arrays $a$ and $b$ are considered different if there exists such a position $i$ that $a_i \neq b_i$.

The number can be pretty large so print it modulo $998244353$.

Input

The first line contains three integers $n$, $k$ and $m$ ($1 \le n \le 5 \cdot 10^5$, $1 \le k \le 30$, $0 \le m \le 5 \cdot 10^5$) — the length of the array $a$, the value such that all numbers in $a$ should be smaller than $2^k$ and the number of conditions, respectively.

Each of the next $m$ lines contains the description of a condition $l_i$, $r_i$ and $x_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i < 2^k$) — the borders of the condition segment and the required bitwise AND value on it.

Output

Print a single integer — the number of distinct arrays $a$ that satisfy all the above conditions modulo $998244353$.

Examples

input

4 3 2
1 3 3
3 4 6

output

input

output

Note

You can recall what is a bitwise AND operation here.

In the first example, the answer is the following arrays: $[3, 3, 7, 6]$, $[3, 7, 7, 6]$ and $[7, 3, 7, 6]$.

Solution:

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=501000;
int n,k,m,cnt[N],ss[N];
ll dp[N],ans=1;
VI l[N];
ll solve(vector<PII> f,vector<int> g) {
int m=SZ(g);
rep(i,1,n+1) ss[i]=0;
for (auto x:g) ss[x]++;
rep(i,1,n+1) ss[i]+=ss[i-1];
rep(i,0,SZ(f)) {
f[i].fi=ss[f[i].fi-1]+1;
f[i].se=ss[f[i].se];
if (f[i].fi>f[i].se) return 0;
}
rep(i,0,m+1) l[i].clear();
for (auto x:f) l[x.se].pb(x.fi);
ll sdp=1;
dp[0]=1;
int posl=0;
rep(i,1,m+1) {
dp[i]=sdp; sdp=sdp*2%mod;
int pr=posl;
for (auto x:l[i]) posl=max(posl,x);
rep(j,pr,posl) {
sdp=(sdp-dp[j])%mod;
dp[j]=0;
}
//rep(j,0,m+1) printf("%lld ",dp[j]); puts("");
}
if (sdp<0) sdp+=mod;
	return sdp;
}

int pl[N],pr[N],x[N];
int main() {
	scanf("%d%d%d",&n,&k,&m);;
	rep(i,0,m) scanf("%d%d%d",pl+i,pr+i,x+i);
	rep(j,0,k) {
		vector<int> g;
vector<PII> cs;
rep(i,1,n+1) cnt[i]=0;
rep(i,0,m) {
if (x[i]&(1<<j)) {
				cnt]++; cnt[pr[i]+1]--;
			} else cs.pb(mp(pl[i],pr[i]));
		}
		rep(i,1,n+1) cnt[i]+=cnt[i-1];
		rep(i,1,n+1) if (cnt[i]==0) g.pb(i);
		ans=ans*solve(cs,g)%mod;
	}
	printf("%lld\n",ans);
}

New Year and Cleaning

Rowena Ravenclaw's Diadem