提出 #61156411

---

ソースコード 拡げる

// 2024/12/28
// ⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠙⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠘⢿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠈⢻⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⢹⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⣶⣿⣿⣥⣤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠈⢻⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣤⣭⠙⢳⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠹⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣯⣴⣾⣿⣿⣿⣶⣶⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠘⣿⣷⢿⣷⡄⠀⠀⠀⠀⣼⣿⠇⠙⢿⣿⣿⡟⣽⠿⠛⠛⢿⣿⡟⠡⣤⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣦⠀⠀⠀⣿⡏⠀⠀⠀⢿⠟⠀⠁⠀⠀⠀⠀⠈⢿⣆⠀⣽⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⡿⠀⠀⢻⡇⠠⣄⡀⠀⠀⠀⠀⢀⣀⠀⠀⠀⠀⣿⡟⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣧⠀⠀⢸⣇⣤⡌⠁⠀⠀⠀⠀⠋⢸⣧⠄⠀⠈⠁⢀⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣤⣾⡄⠁⠀⠀⠛⠛⠛⠀⠀⠈⠉⠀⠀⠀⣾⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⢿⣿⣿⣿⡿⠟⠁⠀⢻⣿⣿⣿⣿⡏⢳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⡟⠛⢹⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠈⠉⠉⠁⠀⠀⠀⠀⠀⣻⣿⣿⣿⡇⠀⠘⠳⢤⣤⣀⣀⠀⠀⣀⣤⡼⢻⣿⠁⠀⣼⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢴⣿⠉⢻⣿⠿⣧⣠⡄⠀⠀⡾⠛⢿⣿⠿⢛⣶⣰⣿⣷⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢴⣿⣿⣿⣿⠇⠸⣿⡇⠀⢸⣣⣴⢞⣿⣤⣿⣿⣿⡏⣹⣻⣾⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣿⣇⠀⠀⣸⣧⠀⣿⣿⣿⣿⣿⣿⣼⣿⣿⡇⣼⣻⣿⡇⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⣿⣿⡄⣸⣿⣿⣧⣿⣿⣾⣿⣿⣷⣿⣿⣿⣿⣦⣝⡿⣷⠀⠀⢀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣧⣿⣿⣿⣿⣿⣿⣿⣟⣼⣿⣿⣿⣿⡇⠘⢿⣽⣿⢷⣀⣾⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⠏⠹⣯⡽⣿⡇⠀⣿⣿⣿⣿⡿⠻⣿⡷⢀⣾⣯⠻⣧⠰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⠏⠀⠀⠙⣿⣍⠃⠀⣿⡟⠿⣧⠀⠀⠟⠁⠘⣿⠙⣦⣿⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠃⠀⠀⠀⠀⢸⣿⣄⢀⣸⣿⣶⣞⣳⣆⠀⠀⢰⣿⡀⣽⡿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⠿⠛⣿⣼⣿⣿⣿⣿⣷⡄⠈⢿⣿⣿⣇⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠉⣀⣽⠾⣿⣿⡏⠛⣿⣿⣿⣿⣆⠀⠻⣿⡿⣍⠹⣿⠲⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣷⠶⣿⣷⣷⣾⣾⣷⣶⣿⣿⣿⣿⣿⣆⠀⢨⣇⠈⣆⣿⡀⠈⠻⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠀⠈⠙⠻⣿⣿⣿⣿⣿⣿⣿⠿⣿⡏⠀⣾⣿⡴⡇⣿⠀⢠⡄⣰⣿⠂⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡟⣿⣄⠀⠀⠀⠈⢹⣿⣿⣿⡿⠛⣿⣿⠁⠀⠛⠋⣿⢀⡏⠀⢸⣯⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⡇⢹⣿⣷⣄⠀⣤⣿⠀⣿⡿⠀⣰⣿⡿⠀⠀⠀⠀⢻⣼⡇⢀⣼⠟⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠇⠠⠀⢿⣿⣿⣿⣿⡏⠀⢻⡇⠀⢸⣿⡇⠀⠀⠀⠀⢀⣿⣴⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣀⡀⢀⣴⣿⣿⣿⣿⠃⠀⢸⣇⣰⣿⡿⠁⠀⠀⠀⢀⣾⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⡟⠛⢿⣿⣿⣿⣿⠀⠀⢸⣿⡙⣿⡇⠀⠀⠀⣴⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣋⣼⡇⠀⠀⢻⣿⣿⣿⠀⠀⢸⣿⣿⣿⣇⣠⣴⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠻⣿⣿⡿⠁⠀⠀⠀⣽⣿⣿⡄⠀⠀⣿⠟⢻⣯⣛⡿⣿⣿⣤⣀⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⠃⢠⡼⠛⠀⠀⠀⠀⠐⣿⣿⣿⣇⠀⠀⢸⡄⢰⡇⠀⣿⣿⣿⡿⠛⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣾⢫⡞⠃⠀⠀⠀⠀⠀⠀⠀⠘⢿⣿⣿⠀⠀⢸⣷⡟⢀⣾⣿⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⡄⠀⢸⢿⡇⣸⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⢀⣴⢛⣾⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⣄⣞⣸⡄⣽⣃⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⣠⣴⣿⣿⣛⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⣿⡇⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠠⠾⠿⠟⠛⠛⠙⠿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠺⠟⠊⠉⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠨⣻⣹⠥⢼⣀⠠⠀⠄⣀⡠⡄⠀⠀⠀⡀⣀

#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[500005],t[500005];

void solve() {
	int k;
	fin>>k>>s>>t;
	int a=strlen(s),b=strlen(t);
	if (a>b) {
		swap(a,b);
		swap(s,t);
	}
	if (b-a>1) {
		fout<<"No\n";
	}
	else {
		bool can=true;
		if (b-a==0) {
			bool dif=false;
			FOR(i,0,a) {
				if (s[i]!=t[i]) {
					if (dif) {
						can=false;
						break;
					}
					dif=true;
				}
			}
		}
		else {
			bool skip=false;
			int tind=0;
			FOR(i,0,a) {
				if (s[i]!=t[tind]) {
					if (skip) {
						can=false;
						break;
					}
					skip=true;
					tind++;
					if (s[i]!=t[tind]) {
						can=false;
						break;
					}
				}
				tind++;
			}
		}
		if (can) {
			fout<<"Yes\n";
		}
		else {
			fout<<"No\n";
		}
	}
}

int main() {
	solve();
	return 0;
}

提出情報

ジャッジ結果