#include<stdio.h>

#include <stdlib.h>

#include<algorithm>

#include<limits.h>

#include<time.h>

#include<iostream>

#include<functional>

#include <fstream>

#include<vector>

#include<queue>

#include<string.h>

#include<stack>

#include <set>

#include<regex>

using namespace std;

#define range(i, s, e) for (int i = (s); i < int(e); i++)

#define range0(i, e) for (int i = 0; i < int(e); i++)

#define input_int(n) int n;scanf("%d",&n);

#define input_int2(n,m) int n;int m;scanf("%d %d",&n,&m);

#define remax(max_record,refresh_number) max_record=std::max(max_record,refresh_number)

#define remin(min_record,refresh_number) min_record=std::min(min_record,refresh_number)

#define INF 0x3f3f3f3f

#define INF2 INT_MAX

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> P;

typedef pair<ll, ll> llP;

inline void read(int &x) {//only read int

}

int BigRand()

{

return RAND_MAX * rand() + rand();

}

int main() {