就是一个模拟吧，没什么好说的

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define x first
#define y second
#define all(x) x.begin(),x.end()

using namespace std;

typedef pair<int,int> PII;

inline int read(){
    char ch = getchar();
    int x = 0;
    int f = 1;
    while(ch > '9' || ch < '0'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void write(int x){
    if(x < 0){
        ...