Submission #62048876
Source Code Expand
// 2024/01/25
// ⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠙⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠘⢿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠈⢻⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⢹⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⣶⣿⣿⣥⣤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠈⢻⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣤⣭⠙⢳⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠹⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣯⣴⣾⣿⣿⣿⣶⣶⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠘⣿⣷⢿⣷⡄⠀⠀⠀⠀⣼⣿⠇⠙⢿⣿⣿⡟⣽⠿⠛⠛⢿⣿⡟⠡⣤⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣦⠀⠀⠀⣿⡏⠀⠀⠀⢿⠟⠀⠁⠀⠀⠀⠀⠈⢿⣆⠀⣽⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⡿⠀⠀⢻⡇⠠⣄⡀⠀⠀⠀⠀⢀⣀⠀⠀⠀⠀⣿⡟⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣧⠀⠀⢸⣇⣤⡌⠁⠀⠀⠀⠀⠋⢸⣧⠄⠀⠈⠁⢀⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⣾⡄⠁⠀⠀⠛⠛⠛⠀⠀⠈⠉⠀⠀⠀⣾⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⢿⣿⣿⣿⡿⠟⠁⠀⢻⣿⣿⣿⣿⡏⢳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡟⠛⢹⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠈⠉⠉⠁⠀⠀⠀⠀⠀⣻⣿⣿⣿⡇⠀⠘⠳⢤⣤⣀⣀⠀⠀⣀⣤⡼⢻⣿⠁⠀⣼⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢴⣿⠉⢻⣿⠿⣧⣠⡄⠀⠀⡾⠛⢿⣿⠿⢛⣶⣰⣿⣷⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢴⣿⣿⣿⣿⠇⠸⣿⡇⠀⢸⣣⣴⢞⣿⣤⣿⣿⣿⡏⣹⣻⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣿⣇⠀⠀⣸⣧⠀⣿⣿⣿⣿⣿⣿⣼⣿⣿⡇⣼⣻⣿⡇⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⣿⣿⡄⣸⣿⣿⣧⣿⣿⣾⣿⣿⣷⣿⣿⣿⣿⣦⣝⡿⣷⠀⠀⢀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣧⣿⣿⣿⣿⣿⣿⣿⣟⣼⣿⣿⣿⣿⡇⠘⢿⣽⣿⢷⣀⣾⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⠏⠹⣯⡽⣿⡇⠀⣿⣿⣿⣿⡿⠻⣿⡷⢀⣾⣯⠻⣧⠰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⠏⠀⠀⠙⣿⣍⠃⠀⣿⡟⠿⣧⠀⠀⠟⠁⠘⣿⠙⣦⣿⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠃⠀⠀⠀⠀⢸⣿⣄⢀⣸⣿⣶⣞⣳⣆⠀⠀⢰⣿⡀⣽⡿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⠿⠛⣿⣼⣿⣿⣿⣿⣷⡄⠈⢿⣿⣿⣇⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠉⣀⣽⠾⣿⣿⡏⠛⣿⣿⣿⣿⣆⠀⠻⣿⡿⣍⠹⣿⠲⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣷⠶⣿⣷⣷⣾⣾⣷⣶⣿⣿⣿⣿⣿⣆⠀⢨⣇⠈⣆⣿⡀⠈⠻⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠀⠈⠙⠻⣿⣿⣿⣿⣿⣿⣿⠿⣿⡏⠀⣾⣿⡴⡇⣿⠀⢠⡄⣰⣿⠂⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡟⣿⣄⠀⠀⠀⠈⢹⣿⣿⣿⡿⠛⣿⣿⠁⠀⠛⠋⣿⢀⡏⠀⢸⣯⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡇⢹⣿⣷⣄⠀⣤⣿⠀⣿⡿⠀⣰⣿⡿⠀⠀⠀⠀⢻⣼⡇⢀⣼⠟⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠇⠠⠀⢿⣿⣿⣿⣿⡏⠀⢻⡇⠀⢸⣿⡇⠀⠀⠀⠀⢀⣿⣴⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣀⡀⢀⣴⣿⣿⣿⣿⠃⠀⢸⣇⣰⣿⡿⠁⠀⠀⠀⢀⣾⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⡟⠛⢿⣿⣿⣿⣿⠀⠀⢸⣿⡙⣿⡇⠀⠀⠀⣴⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣋⣼⡇⠀⠀⢻⣿⣿⣿⠀⠀⢸⣿⣿⣿⣇⣠⣴⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠻⣿⣿⡿⠁⠀⠀⠀⣽⣿⣿⡄⠀⠀⣿⠟⢻⣯⣛⡿⣿⣿⣤⣀⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⠃⢠⡼⠛⠀⠀⠀⠀⠐⣿⣿⣿⣇⠀⠀⢸⡄⢰⡇⠀⣿⣿⣿⡿⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣾⢫⡞⠃⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⠀⠀⢸⣷⡟⢀⣾⣿⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⡄⠀⢸⢿⡇⣸⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⢀⣴⢛⣾⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⣄⣞⣸⡄⣽⣃⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⣠⣴⣿⣿⣛⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⡇⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠠⠾⠿⠟⠛⠛⠙⠿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠺⠟⠊⠉⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠨⣻⣹⠥⢼⣀⠠⠀⠄⣀⡠⡄⠀⠀⠀⡀⣀
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long MOD2 = 998244353;
#define ll long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
#define FOR1(i, b) for (auto i = 1; i <= (b); ++i)
#define FORR(i, a) for (auto (i) : (a))
#define ld long double
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define pqi priority_queue<int>
#define pqll priority_queue<ll>
#define dqi deque<int>
#define dqll deque<ll>
// Credit to: https://github.com/emeraldacoustics/fast-io
class fistream
{
public:
static const int bufsz = 1 << 16;
class buffer
{
public:
int isz;
char ibuf[bufsz];
};
FILE * pin;
stack<buffer> ibuf_stk;
int ipt, isz;
char ibuf[bufsz];
char word[64];
fistream();
fistream(FILE *);
operator bool ();
void stack_buffer();
void next_buffer();
bool trim();
bool integral();
bool floating();
bool getline(char *, const int &);
bool eof();
void putback(const char &);
fistream & operator >> (char &);
fistream & operator >> (char *);
fistream & operator >> (int &);
fistream & operator >> (unsigned int &);
fistream & operator >> (long long &);
fistream & operator >> (unsigned long long &);
fistream & operator >> (__int128 &);
fistream & operator >> (unsigned __int128 &);
fistream & operator >> (float &);
fistream & operator >> (double &);
fistream & operator >> (long double &);
} fin(stdin), fin_null(0);
fistream::fistream() : pin(0), ipt(bufsz), isz(bufsz)
{
}
fistream::fistream(FILE * pin) : pin(pin), ipt(bufsz), isz(bufsz)
{
}
inline fistream::operator bool ()
{
return this != &fin_null;
}
inline void fistream::stack_buffer()
{
if (ipt == 0)
{
ibuf_stk.push(buffer());
ibuf_stk.top().isz = isz;
memcpy(ibuf_stk.top().ibuf, ibuf, sizeof ibuf[0] * isz);
isz = bufsz;
ipt = isz;
}
}
inline void fistream::next_buffer()
{
if (ibuf_stk.empty())
isz = fread(ibuf, 1, bufsz, pin);
else
{
isz = ibuf_stk.top().isz;
memcpy(ibuf, ibuf_stk.top().ibuf, sizeof ibuf[0] * isz);
ibuf_stk.pop();
}
ipt = 0;
}
inline bool fistream::trim()
{
for (; isz > 0; next_buffer())
{
for (; ipt < isz && ibuf[ipt] <= ' '; ipt++);
if (ipt < isz)
break;
}
return eof();
}
inline bool fistream::integral()
{
if (trim())
return false;
int len = 0;
bool vld = false;
if (ibuf[ipt] == '-' || ibuf[ipt] == '+')
word[len++] = ibuf[ipt++];
for (; isz > 0; next_buffer())
{
for (; ipt < isz && isdigit(ibuf[ipt]); ipt++)
{
word[len++] = ibuf[ipt];
vld = true;
}
if (ipt < isz)
break;
}
word[len] = 0;
return vld;
}
inline bool fistream::floating()
{
if (trim())
return false;
int len = 0;
bool vld = false, rht = false;
if (ibuf[ipt] == '-' || ibuf[ipt] == '+')
word[len++] = ibuf[ipt++];
for (; isz > 0; next_buffer())
{
for (; ipt < isz && (isdigit(ibuf[ipt]) || ibuf[ipt] == '.'); ipt++)
{
if (ibuf[ipt] == '.')
{
if (rht)
break;
else
rht = true;
}
else
vld = true;
word[len++] = ibuf[ipt];
}
if (ipt < isz)
break;
}
word[len] = 0;
return vld;
}
inline bool fistream::getline(char * s, const int & n)
{
if (this == &fin_null || eof())
return false;
int slen = 0;
for (; isz > 0; next_buffer())
{
for (; ipt < isz && slen < n - 1 && ibuf[ipt] != '\n'; ipt++)
s[slen++] = ibuf[ipt];
if (ipt < isz)
break;
}
s[slen] = 0;
for (; isz > 0 && ipt == isz; next_buffer());
if (ipt < isz && ibuf[ipt] == '\n')
ipt++;
return true;
}
inline bool fistream::eof()
{
for (; isz > 0 && ipt == isz; next_buffer());
return isz == 0;
}
inline void fistream::putback(const char & c)
{
if (ipt == 0)
stack_buffer();
ibuf[--ipt] = c;
}
inline fistream & fistream::operator >> (char & c)
{
if (this == &fin_null || trim())
return fin_null;
else
{
c = ibuf[ipt++];
return *this;
}
}
inline fistream & fistream::operator >> (char * s)
{
if (this == &fin_null || trim())
return fin_null;
int slen = 0;
for (; isz > 0; next_buffer())
{
for (; ipt < isz && ibuf[ipt] > ' '; ipt++)
s[slen++] = ibuf[ipt];
if (ipt < isz)
break;
}
s[slen] = 0;
return *this;
}
inline fistream & fistream::operator >> (int & x)
{
if (this == &fin_null || !(this->integral()))
return fin_null;
int i = 0, sgn;
int ans = 0;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
ans = ans * 10 + word[i] - '0';
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (unsigned int & x)
{
if (this == &fin_null || !(this->integral()))
return fin_null;
int i = 0, sgn;
int ans = 0;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
ans = ans * 10 + word[i] - '0';
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (long long & x)
{
if (this == &fin_null || !(this->integral()))
return fin_null;
int i = 0, sgn;
long long ans = 0;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
ans = ans * 10 + word[i] - '0';
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (unsigned long long & x)
{
if (this == &fin_null || !(this->integral()))
return fin_null;
int i = 0, sgn;
long long ans = 0;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
ans = ans * 10 + word[i] - '0';
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (__int128 & x)
{
if (this == &fin_null || !(this->integral()))
return fin_null;
int i = 0, sgn;
__int128 ans = 0;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
ans = ans * 10 + word[i] - '0';
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (unsigned __int128 & x)
{
if (this == &fin_null || !(this->integral()))
return fin_null;
int i = 0, sgn;
__int128 ans = 0;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
ans = ans * 10 + word[i] - '0';
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (float & x)
{
if (this == &fin_null || !(this->floating()))
return fin_null;
int i = 0, sgn;
bool vis = false;
float ans = 0, factor = 1;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
{
if (word[i] == '.')
{
vis = true;
continue;
}
if (!vis)
ans = ans * 10 + word[i] - '0';
else
{
factor /= 10;
ans += factor * (word[i] - '0');
}
}
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (double & x)
{
if (this == &fin_null || !(this->floating()))
return fin_null;
int i = 0, sgn;
bool vis = false;
double ans = 0, factor = 1;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
{
if (word[i] == '.')
{
vis = true;
continue;
}
if (!vis)
ans = ans * 10 + word[i] - '0';
else
{
factor /= 10;
ans += factor * (word[i] - '0');
}
}
x = ans * sgn;
return *this;
}
inline fistream & fistream::operator >> (long double & x)
{
if (this == &fin_null || !(this->floating()))
return fin_null;
int i = 0, sgn;
bool vis = false;
long double ans = 0, factor = 1;
if (word[0] == '-')
sgn = -1, i++;
else if (word[0] == '+')
sgn = 1, i++;
else
sgn = 1;
for (; word[i]; i++)
{
if (word[i] == '.')
{
vis = true;
continue;
}
if (!vis)
ans = ans * 10 + word[i] - '0';
else
{
factor /= 10;
ans += factor * (word[i] - '0');
}
}
x = ans * sgn;
return *this;
}
class fostream
{
public:
static const int bufsz = 1 << 16;
FILE * pout;
int opt;
char obuf[bufsz];
char word[64];
int pcs;
string format_float, format_double, format_long_double;
class precision
{
public:
int pcs;
precision() : pcs(0)
{
}
precision(const int & pcs) : pcs(pcs)
{
}
};
fostream();
fostream(FILE *);
~fostream();
void fprecision(const int &);
fostream & operator << (const precision &);
fostream & operator << (const char &);
fostream & operator << (const char *);
fostream & operator << (const int &);
fostream & operator << (const unsigned int &);
fostream & operator << (const long long &);
fostream & operator << (const unsigned long long &);
fostream & operator << (const __int128 &);
fostream & operator << (const unsigned __int128 &);
fostream & operator << (const float &);
fostream & operator << (const double &);
fostream & operator << (const long double &);
void flush();
} fout(stdout), ferr(stderr);
const char fendl = '\n';
fostream::fostream() : pout(0), opt(0), pcs(3), format_float("%.3f"), format_double("%.3lf"), format_long_double("%.3Lf")
{
}
fostream::fostream(FILE * pout) : pout(pout), opt(0), pcs(3), format_float("%.3f"), format_double("%.3lf"), format_long_double("%.3Lf")
{
}
fostream::~fostream()
{
flush();
}
inline void fostream::fprecision(const int & x)
{
pcs = x;
sprintf(word, "%%.%d", pcs);
(format_float = word) += "f";
(format_double = word) += "lf";
(format_long_double = word) += "Lf";
}
inline fostream & fostream::operator << (const precision & rhs)
{
fprecision(rhs.pcs);
return *this;
}
inline fostream & fostream::operator << (const char & c)
{
obuf[opt++] = c;
if (opt == bufsz)
flush();
return *this;
}
inline fostream & fostream::operator << (const char * s)
{
for (int i = 0; s[i]; i++)
{
obuf[opt++] = s[i];
if (opt == bufsz)
flush();
}
return *this;
}
inline fostream & fostream::operator << (const int & x)
{
int len = 0;
unsigned int y;
if (x < 0)
word[len++] = '-', y = -x;
else
y = x;
if (y == 0)
word[len++] = '0';
else
{
for (; y > 0; y /= 10)
word[len++] = '0' + y % 10;
}
reverse(word + (x < 0 ? 1 : 0), word + len);
word[len] = 0;
*this << word;
return *this;
}
inline fostream & fostream::operator << (const unsigned int & x)
{
int len = 0;
if (x == 0)
word[len++] = '0';
else
{
for (unsigned int y = x; y > 0; y /= 10)
word[len++] = '0' + y % 10;
}
reverse(word, word + len);
word[len] = 0;
*this << word;
return *this;
}
inline fostream & fostream::operator << (const long long & x)
{
int len = 0;
unsigned long long y;
if (x < 0)
word[len++] = '-', y = -x;
else
y = x;
if (y == 0)
word[len++] = '0';
else
{
for (; y > 0; y /= 10)
word[len++] = '0' + y % 10;
}
reverse(word + (x < 0 ? 1 : 0), word + len);
word[len] = 0;
*this << word;
return *this;
}
inline fostream & fostream::operator << (const unsigned long long & x)
{
int len = 0;
if (x == 0)
word[len++] = '0';
else
{
for (unsigned long long y = x; y > 0; y /= 10)
word[len++] = '0' + y % 10;
}
reverse(word, word + len);
word[len] = 0;
*this << word;
return *this;
}
inline fostream & fostream::operator << (const __int128 & x)
{
int len = 0;
unsigned __int128 y;
if (x < 0)
word[len++] = '-', y = -x;
else
y = x;
if (y == 0)
word[len++] = '0';
else
{
for (; y > 0; y /= 10)
word[len++] = '0' + y % 10;
}
reverse(word + (x < 0 ? 1 : 0), word + len);
word[len] = 0;
*this << word;
return *this;
}
inline fostream & fostream::operator << (const unsigned __int128 & x)
{
int len = 0;
if (x == 0)
word[len++] = '0';
else
{
for (unsigned __int128 y = x; y > 0; y /= 10)
word[len++] = '0' + y % 10;
}
reverse(word, word + len);
word[len] = 0;
*this << word;
return *this;
}
inline fostream & fostream::operator << (const float & x)
{
sprintf(word, format_float.c_str(), x);
*this << word;
return *this;
}
inline fostream & fostream::operator << (const double & x)
{
sprintf(word, format_double.c_str(), x);
*this << word;
return *this;
}
inline fostream & fostream::operator << (const long double & x)
{
sprintf(word, format_long_double.c_str(), x);
*this << word;
return *this;
}
inline void fostream::flush()
{
if (opt > 0)
{
fwrite(obuf, 1, opt, pout);
opt = 0;
}
}
inline fostream::precision fsetprecision(const int & x)
{
return fostream::precision(x);
}
// Credit to maroonrk:
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
using uint=unsigned;
using ull=unsigned long long;
int topbit(signed t){
return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
return __builtin_popcount(t);
}
int popcount(ll t){
return __builtin_popcountll(t);
}
int popcount(ull t){
return __builtin_popcountll(t);
}
bool ispow2(int i){
return i&&(i&-i)==i;
}
ll mask(int i){
return ((ll)(1)<<i)-1;
}
ull umask(int i){
return ((ull)(1)<<i)-1;
}
bool inc(int a,int b,int c){
return a<=b&&b<=c;
}
char s[1005][1005];
void solve() {
int h,w;
fin>>h>>w;
bool has=false;
int minh=10000,minw=10000,maxh=-1,maxw=-1;
FOR(i,0,h) {
fin>>s[i];
FOR(j,0,w) {
if (s[i][j]=='#') {
has=true;
minh=min(minh,i);
minw=min(minw,j);
maxh=max(maxh,i);
maxw=max(maxw,j);
}
}
}
if (!has) {
fout<<"Yes\n";
return;
}
FOR(i,minh,maxh+1) {
FOR(j,minw,maxw+1) {
if (s[i][j]=='.') {
fout<<"No\n";
return;
}
}
}
fout<<"Yes\n";
}
int main() {
solve();
return 0;
}
Submission Info
Compile Error
Main.cpp: In function ‘void solve()’:
Main.cpp:816:13: warning: ‘h’ may be used uninitialized [-Wmaybe-uninitialized]
816 | int h,w;
| ^
Main.cpp:816:15: warning: ‘w’ may be used uninitialized [-Wmaybe-uninitialized]
816 | int h,w;
| ^
Judge Result
| Set Name |
Sample |
All |
| Score / Max Score |
0 / 0 |
300 / 300 |
| Status |
|
|
| Set Name |
Test Cases |
| Sample |
example_00.txt, example_01.txt, example_02.txt |
| All |
example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt |
| Case Name |
Status |
Exec Time |
Memory |
| example_00.txt |
AC |
1 ms |
3556 KiB |
| example_01.txt |
AC |
1 ms |
3636 KiB |
| example_02.txt |
AC |
1 ms |
3428 KiB |
| hand_00.txt |
AC |
4 ms |
4600 KiB |
| hand_01.txt |
AC |
3 ms |
4564 KiB |
| hand_02.txt |
AC |
3 ms |
4472 KiB |
| hand_03.txt |
AC |
3 ms |
4588 KiB |
| hand_04.txt |
AC |
3 ms |
4528 KiB |
| hand_05.txt |
AC |
1 ms |
3564 KiB |
| hand_06.txt |
AC |
1 ms |
3436 KiB |
| hand_07.txt |
AC |
1 ms |
3504 KiB |
| hand_08.txt |
AC |
2 ms |
4552 KiB |
| hand_09.txt |
AC |
4 ms |
4676 KiB |
| hand_10.txt |
AC |
3 ms |
4608 KiB |
| hand_11.txt |
AC |
3 ms |
4604 KiB |
| hand_12.txt |
AC |
4 ms |
4516 KiB |
| random_00.txt |
AC |
4 ms |
4508 KiB |
| random_01.txt |
AC |
6 ms |
4516 KiB |
| random_02.txt |
AC |
3 ms |
4476 KiB |
| random_03.txt |
AC |
6 ms |
4744 KiB |
| random_04.txt |
AC |
6 ms |
4576 KiB |
| random_05.txt |
AC |
3 ms |
4640 KiB |
| random_06.txt |
AC |
3 ms |
4464 KiB |
| random_07.txt |
AC |
3 ms |
4516 KiB |
| random_08.txt |
AC |
3 ms |
4532 KiB |
| random_09.txt |
AC |
3 ms |
4520 KiB |
| random_10.txt |
AC |
3 ms |
4520 KiB |
| random_11.txt |
AC |
3 ms |
4544 KiB |
| random_12.txt |
AC |
3 ms |
4488 KiB |
| random_13.txt |
AC |
4 ms |
4512 KiB |
| random_14.txt |
AC |
3 ms |
4528 KiB |
| random_15.txt |
AC |
3 ms |
4520 KiB |
| random_16.txt |
AC |
4 ms |
4392 KiB |
| random_17.txt |
AC |
3 ms |
4480 KiB |
| random_18.txt |
AC |
3 ms |
4484 KiB |
| random_19.txt |
AC |
4 ms |
4572 KiB |
| random_20.txt |
AC |
3 ms |
4636 KiB |
| random_21.txt |
AC |
3 ms |
4556 KiB |
| random_22.txt |
AC |
4 ms |
4592 KiB |
| random_23.txt |
AC |
3 ms |
4724 KiB |
| random_24.txt |
AC |
3 ms |
4580 KiB |