//I
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
int T, n, m;
int a[maxn];
int solve1()
{
int res = ((a[1] + m < a[2]) ? 1 : 0);
int now = a[1] + m;
for (int i = 3; i <= (n << 1); i += 2)
{
int mn = min(a[i], a[i + 1]);
int mx = max(a[i], a[i + 1]); if (mn > now)
res += 2;
if (mn <= now && mx > now)
res++;
if (mx <= now)
{
int need = m - (now - mx) - (now - mn);
if (need > 0)
res++;
}
}
return res;
}
int solve2()
{
int res = ((a[1] < a[2] + m) ? 1 : 0), now = a[1]; for (int i = 3; i <= (n << 1); i += 2)
{
int mn = min(a[i], a[i + 1]);
int mx = max(a[i], a[i + 1]); if (mn > now) res += 2;
if (mn <= now && mx > now) res += 1 + ((now - mn < m) ? 1 : 0);
if (mx <= now)
{
if (now - mx < m)
res++;
if (m - (now - mx) > now - mn)
res++;
}
}
return res;
}
int main()
{
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = 1; i <= (n << 1); i++)
cin >> a[i];
cout << solve1() << ' ' << solve2() << '\n';
}
return 0;
}
//G
#include<bits/stdc++.h>
using namespace std;
int a, b, c;
int main()
{
cin >> a >> b >> c;
int m = max(b, a + 1);
// x1
cout << 1;
for (int i = 1; i <= m - 2; i++)
cout << 0;
cout << 1;
for (int i = 1; i <= a; i++)
cout << 0;
cout << ' ';
// y1
for (int i = 1; i <= m; i++)
cout << 9;
cout << ' ';
// x2
cout << 1;
for (int i = 1; i <= a + m - 1; i++)
cout << 0;
cout << ' ';
// y2
for (int i = 1; i <= m; i++)
cout << 9;
return 0;
}
//B
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int md=998244353;
int T,n,m,a[100010],f[100010],dp[100010],dpp[100010];
signed main(){
ios::sync_with_stdio(0);
cin>>T;
while(T--){
cin>>n>>m;
bool fl=0;
for(int i=0;i<=n*2+1;i++){
f[i]=dp[i]=dpp[i]=0;
}
for(int i=1;i<=m;i++){
cin>>a[i];
if(a[i]<1||a[i]>2*n){
fl=1;
}
}
if(fl){
cout<<0<<endl;
continue;
}
for(int i=1;i<=m;i++){
if(f[a[i]]){
fl=1;
}
f[a[i]]=1;
}
if(fl){
cout<<0<<endl;
continue;
}
dp[0]=1;
for(int pos=1;pos<=2*n;pos++){
for(int i=0;i<=n;i++){
dpp[i]=0;
}
for(int j=0;j<=n;j++){
if(dp[j]==0){
continue;
}
if(!f[pos]){
if(2*j>=pos){
dpp[j]=(dpp[j]+dp[j])%md;
}
}
if(j+1<=n){
int nj=j+1;
if(2*nj>=pos){
dpp[nj]=(dpp[nj]+dp[j])%md;
}
}
}
for(int i=0;i<=n;i++){
dp[i]=dpp[i];
}
}
cout<<dp[n]%md<<endl;
}
return 0;
}
//H
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
const int mod = 998244353;
int T, n, x;
int a[maxn];
void write(__int128 x)
{
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}void solve()
{
__int128 ans = 0, t = 0;
cin >> n >> x;
for (int i = 1; i <= n; i++)
cin >> a[i];
if (x == 1)
{
for (int i = 1; i <= n; i++)
ans = (ans + a[i]) % mod;
write(ans);
putchar('\n');
return ;
}
for (int i = 1; i <= n; i++)
{
t += a[i] / x;
a[i] %= x;
}
sort (a + 1, a + n + 1);
for (int i = n; i >= 1; i--)
{
if (!a[i]) continue;
int need = x - a[i] - 1;
if (need <= t)
{
t -= need;
a[i] = 0;
}
else break;
}
for (int i = 1; i <= n; i++)
ans = (ans + a[i]) % mod;
write((ans + t % (x - 1)) % mod);
putchar('\n');
return ;
}
signed main()
{
cin >> T;
while (T--)
solve();
return 0;
}
//K
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e17;
int T,n,a,b,k,tot,s,t,cnt,hed[100010],ver[100010],nxt[100010],edg[100010];
int dis[100010],pre[100010],incf[100010],inq[100010],cost[100010];
int pa[100010],ca[100010],pb[100010],cb[100010];
int h[100010],ansflow,anscost;
void add(int a,int b,int c,int d){
ver[++tot]=b,nxt[tot]=hed[a],hed[a]=tot,edg[tot]=c,cost[tot]=d;
ver[++tot]=a,nxt[tot]=hed[b],hed[b]=tot,edg[tot]=0,cost[tot]=-d;
}
bool spfa(){
queue<int> q;
for(int i=0;i<=cnt;i++){
dis[i]=inf;
inq[i]=0;
}
dis[s]=0;
q.push(s);
inq[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=hed[u];i;i=nxt[i]){
int v=ver[i];
if(edg[i]>0&&dis[v]>dis[u]+cost[i]){
dis[v]=dis[u]+cost[i];
if(!inq[v]){
q.push(v);
inq[v]=1;
}
}
}
}
for(int i=0;i<=cnt;i++){
h[i]=(dis[i]==inf?0:dis[i]);
}
return dis[t]!=inf;
}
bool dijkstra(){
priority_queue<pair<int, int> > q;
for(int i=0;i<=cnt;i++){
dis[i]=inf;
pre[i]=incf[i]=0;
}
dis[s]=0;
incf[s]=inf;
q.push({0,s});
while(!q.empty()){
int d=-q.top().first,u=q.top().second;
q.pop();
if(dis[u]!=d){
continue;
}
for(int i=hed[u];i;i=nxt[i]){
int v=ver[i];
if(edg[i]>0){
int nd=d+cost[i]+h[u]-h[v];
if(dis[v]>nd){
dis[v]=nd;
pre[v]=i;
incf[v]=min(incf[u],edg[i]);
q.push({-nd,v});
}
}
}
}
return dis[t]!=inf;
}
void solve(){
cin>>n>>a>>b>>k;
for(int i=1;i<=a;i++){
cin>>pa[i]>>ca[i];
}
for(int i=1;i<=b;i++){
cin>>pb[i]>>cb[i];
}
//Ain=1+(u-1)*2,out=in+1
//Bin=a*2+(v-1)*2+1,out=in+1
s=0,t=a*2+b*2+1;
cnt=2*a+2*b+1,tot=1,anscost=0,ansflow=0;
for(int i=0;i<=cnt;i++){
hed[i]=0;
}
for(int u=1;u<=a;u++){
add(u*2-1,u*2,ca[u],0);
if(pa[u]==0){
add(s,u*2-1,inf,0);
continue;
}
add(pa[u]*2,u*2-1,inf,0);
}
for(int v=1;v<=b;v++){
add(a*2+v*2-1,a*2+v*2,cb[v],0);
if(pb[v]==0){
add(a*2+v*2,t,inf,0);
continue;
}
add(a*2+v*2,a*2+pb[v]*2-1,inf,0);
}
for(int i=1;i<=n;i++){
int x,y,w;
cin>>x>>y>>w;
add(x*2,a*2+y*2-1,1,-w);
}
if(k==0){
cout<<0<<endl;
return ;
}
if(!spfa()){
cout<<-1<<endl;
return;
}
while(ansflow<k&&dijkstra()){
for(int i=0;i<=cnt;i++){
if(dis[i]<inf){
h[i]+=dis[i];
}
}
int f=incf[t];
if(f>k-ansflow){
f=k-ansflow;
}
for(int i=t;i!=s;i=ver[pre[i]^1]){
edg[pre[i]]-=f;
edg[pre[i]^1]+=f;
}
ansflow+=f;
anscost+=f*(h[t]-h[s]);
}
if(ansflow<k){
cout<<-1<<endl;
return ;
}
cout<<-anscost<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin>>T;
while(T--){
solve();
}
return 0;
}
