$$\huge{请调整至浅色背景以获得更好的阅览效果}$$

/*................................................................................[膜拜奆佬，程序AC].................................................................................................*/
#pragma GCC optimize(2)/*.....................................................]]@@@@@@@@@@@@@@@@@@@@@@@@`............................................................................................*/
#pragma GCC optimize(3)/*..............................................]]@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@`..........................................................................................*/
#pragma GCC optimize("Ofast")/*...................................../@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@`........................................................................................*/
#pragma GCC optimize("inline")/*................................../@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@`....................................../$$$$$$/$$$$....................................*/
#pragma GCC optimize("-fgcse")/*...............................,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\....................................| $$_  $$_  $$...................................*/
#pragma GCC optimize("-fgcse-lm")/*..........................,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\..................................| $$.\ $$.\ $$...................................*/
#pragma GCC optimize("-fipa-sra")/*........................,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\................................| $$.| $$.| $$...................................*/
#pragma GCC optimize("-ftree-pre")/*.....................,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^..............................| $$.| $$.| $$...................................*/
#pragma GCC optimize("-ftree-vrp")/*...................../@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^.............................\__/.|__/.|__/...................................*/
#pragma GCC optimize("-fpeephole2")/*....................@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\..............................................................................*/
#pragma GCC optimize("-ffast-math")/*.................../@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@................................/$$$$$$......................................*/
#pragma GCC optimize("-fsched-spec")/*................./@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.............................../$$__  $$.....................................*/
#pragma GCC optimize("unroll-loops")/*................@@@@@@@@@@@OOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@..............................| $$  \ $$.....................................*/
#pragma GCC optimize("-falign-jumps")/*..............@@@@@@@@@@OOOooooooooooooooOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@..............................| $$  | $$.....................................*/
#pragma GCC optimize("-falign-loops")/*..............@@@@@@@@OOOoooooooooooooOooooOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@..............................|  $$$$$$/.....................................*/
#pragma GCC optimize("-falign-labels")/*.............@@@@@@@@OOOooooooooooooooooooOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@^..............................\______/.......................................*/
#pragma GCC optimize("-fdevirtualize")/*.............\@@@@@@@OOOooooooOoooOoooooooOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@^.............................................................................*/
#pragma GCC optimize("-fcaller-saves")/*.............,@@@@@@OOOOooooooooooooooooooOOoooooOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@....................................../$$.....................................*/
#pragma GCC optimize("-fcrossjumping")/*..............=@@@@@OOOOoooooooooooooooOooOooooooOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@.....................................|.$$.....................................*/
#pragma GCC optimize("-fthread-jumps")/*................\@@OOOOOOOoooooOOoooooOOOooooooOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@................................../$$$$$$$.....................................*/
#pragma GCC optimize("-funroll-loops")/*..................@OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@^................................./$$__  $$.....................................*/
#pragma GCC optimize("-fwhole-program")/*.................@OOOO@@@@@@@@@@@@@@@OOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.................................| $$..| $$.....................................*/
#pragma GCC optimize("-freorder-blocks")/*..............]@@OOO@@OOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@..................................| $$..| $$.....................................*/
#pragma GCC optimize("-fschedule-insns")/*.............OOOOOOOOOOOOOO@@@@@@@@@@@@OO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\..............................| $$$$$$$......................................*/
#pragma GCC optimize("inline-functions")/*............=@@@@@@OOO@@@@@@@@@@@@@@@@@OO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\.............................\_______/......................................*/
#pragma GCC optimize("-ftree-tail-merge")/*...........=@@@@@@OOOOOOOO@@@@@@@OOO@@OO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@............................................................................*/
#pragma GCC optimize("-fschedule-insns2")/*...........=@OO@@OOOOOOOOOOOOOO@OOO@@OOOO@@@@@@OOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@............................................................................*/
#pragma GCC optimize("-fstrict-aliasing")/*...........OOOOOOOOOOOOOOOOO@OOOOOOOooOOO@@@@@@OOO@@@@@OO@@@@@@@@@@@@@@@@@@@^.............................................................................*/
#pragma GCC optimize("-fstrict-overflow")/*............=OOOOOOOoooOOOOOOOOOOOOOoooOOOO@@@@@@OOOOOOOOO@@@@@@@@@@@@@@@@@@/.............................................................................*/
#pragma GCC optimize("-falign-functions")/*.............OOOOOOOOoOOOOOOOOOOOOOOoooOOO@@@@@@OOOOOOOOOOO@@@@@@@@@@@@@@@@@`.............................................................................*/
#pragma GCC optimize("-fcse-skip-blocks")/*.............=OOOOOOOoooOOOOOOOOOOoooooOOO@@@@@@@OOOOOOOOO@@@@@@@@@@@@@@@@@@..............................................................................*/
#pragma GCC optimize("-fcse-follow-jumps")/*.............OOOOOOOoooooooOOOOOoOOOOOO@@@@@@@@@OOOOOOOOO@@@@@@@@@@@@@@@@@`..............................................................................*/
#pragma GCC optimize("-fsched-interblock")/*.............OOOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@OOOOO@@@@@@@@@@@@@@@@@[................................................................................*/
#pragma GCC optimize("-fpartial-inlining")/*.............@@OOOOOOOOOOOOOoooOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@`..................................................................................*/
#pragma GCC optimize("no-stack-protector")/*..............\OOOOOOOOOOOOoooooooOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@/...................................................................................*/
#pragma GCC optimize("-freorder-functions")/*..............OOOOOOOOOOOOOoooOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@^...................................................................................*/
#pragma GCC optimize("-findirect-inlining")/*..............OOOOOOOOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@O....................................................................................*/
#pragma GCC optimize("-fhoist-adjacent-loads")/*...........=OOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^....................................................................................*/
#pragma GCC optimize("-frerun-cse-after-loop")/*...........,OOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.....................................................................................*/
#pragma GCC optimize("inline-small-functions")/*............OOOOOOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@^.....................................................................................*/
#pragma GCC optimize("-finline-small-functions")/*..........,OOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@`.....................................................................................*/
#pragma GCC optimize("-ftree-switch-conversion")/*...........=OOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^......................................................................................*/
#pragma GCC optimize("-foptimize-sibling-calls")/*............\@OOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@.......................................................................................*/
#pragma GCC optimize("-fexpensive-optimizations")/*............,OOOOOOOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@/.......................................................................................*/
#pragma GCC optimize("-funsafe-loop-optimizations")/*............\@@@OOOOOOOOOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@\.......................................................................................*/
#pragma GCC optimize("inline-functions-called-once")/*............,O@@OOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@^O.....................................................................................*/
#pragma GCC optimize("-fdelete-null-pointer-checks")/*..............\OOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\....................................................................................*/
#pragma comment(linker, "/STACK:102400000,102400000")/*.............=OOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OOO\`.................................................................................*/
#pragma GCC diagnostic error "-std=c++11"/*........................,OOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OOOOOO\................................................................................*/
#pragma GCC -mcmodle=large/*.......................................oO@OOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@@@@OOOOOOOO@\...............................................................................*/
/*................................................................==@@OOOOOOOOOOO@@@@@@@@@@@@@@@@@@@@@@@@@OOOOOOOOOOOO\................................................................................
..................................................................\=@@@OOOooOOOOOOOO@@@@@@@@@@@@@@@@@@@@@OOOOOOOOOOOOOOOOOO]`..........................................................................
.................................................................O^.\@@OOooooOOOOOOOOOOOOOOOOOOOOO@@@@@OOOOOOOOOOOOOOOOOOOOOOOOO]......................................................................
...............................................................]**...O@@OoooooOOOOOOOOOOOOOOOOOOOO@@@OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\`.................................................................
...........................................................,[.........O@OOOooooOOOOOOOOOOOOOOOOOOO@OOoOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO\`.............................................................
........................................................*[............*\@@OOooooOOOOOOOOOOOOOOOOOOoooOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOoooooooOO].........................................................
.....................................................*.................*O@@OOOOOOOOOOOOOOOOOOOOoOooooOOOOOOOOOOOOOOOOOOOOOOOOOOOOOoooooooooo[[,\O\`....................................................
................................................**..................,O@\\O@@OOOOOOOOOOOOOOOOOOOOOOoOOOOOOOOOOOOOOOOOOOOOOOOOOOoooooooooooooo]*.....*\].................................................
............................................``.....................=@@@@@OoO@OOOOOOOOOOOOOOO@@@@@OoOOOOOOOOOOOOOOOOOOOOOOOOOooooooooooooooooooo`*...**.,o\`............................................
.......................................,*........................./@@@@@@@@@@OOOOOOOOOO@@@@@@@@@@@OOOOOooOOOOOoooOOOOOOOOooooo/ooo[[*,[\[[[[ooo[`........*,\O^..]]`....................................
....................................,/.........................../@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OoooooooooooOOOOoOOoooooo^...............................**[\oooOO`................................
.................................=/............................./@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@OoooooooooOOOOooo\**,\....................................******,\O`..............................
..............................,/`..............................=O@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@Ooooo`=OOOO/`.............................................*=oo^/oO\.............................
............................*..................................=O@@@@OOoO@@@@@@@@@@@@@@@@@@@@@@@OOO@@OOOOoo`=oOOo\..............................................*=oooooOOOO`...........................
..........................,...................................,OOOO/`*..,@@@@@@@@@@@@@@@@@@@@@@OOOOOooo/[[oooooo^................................................ooooooOOOO@^..........................
........................,/.....................................*`........\@@@@@@@@@@@@@@@@@@@@OOOOoo.............................................................oOooooOOOOO@^.........................
........................^.................................................@@@@@@@@@@@@@@@@@@OOOOOo\..............................................................oOOoooOOOOOO@\........................
.......................=*.................................................O@@@@@@@@@@@@@@@@OOOOOo^............................................................**,oOOoooOOOOOOO@O.......................
.......................^..................................................O@@@@@@@@@@@@@@@OOOOOo^.............................................................,/,oOOoooOOOOOOOO@@......................
......................=...................................................O@@@@@@@@@@@@@@@OOOOo^.............................................................*\`*]oOOOOOOOOOOOOO@@.....................
......................^..................................................=@@@@@@@@@@@@@@@@OOOoo...............................................................*OOOOOOOOOOOOOOOOOO@@....................
.....................O^.................................................,@@@@@@@@@@@@@@@@@OOOo\..............................................................=OOOooOOOOOOOOOOOOOOO@@...................
.....................O*.................................................O@@@@@@@@@@@@@@@@@OOOo..............................................................*oOOOooOOOOOOOOOOOOOOO@@...................
....................,^................................................./@@@@@@@@@@@@@@@@@OOOOo^............................................................\OOOOooOOOOOOOOOOOOOOOO@@...................
....................=^.................................................O@@@@@@@@@@@@@@@@@@OOOOo^*.......................................................`**\OOOOOoOOOOOOOOOOOOOOOOO@@..................
.....................*................................................=@@@@@@@@@@@@@@@@@@@OOOOo\*....................................................\ooo*,oOOOOooOOOOOOOOOOOOOOOOO@@.................
.....................*...............................................,O@@@@@@@@@@@@@@@@@@@OOOOOo*.........................................................oooOOOoooooOOOOOOOoooooOO@@..................
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO.
.......................................................................................................................................................................................................
.......................................................................................................................................................................................................
.......................................................................................................................................................................................................
.......................................................................................................................................................................................................
.................................................$$\.............................................$\....................................................................................................
.................................................$$\.............................................&&\...................................................................................................
.................................................$$\.............................................&&.\..................................................................................................
.................................................$$|.............................................$$.|..................................................................................................
..................................$$$$$$$\.......$$$$$$$\........$$\...$$\.......$$\...$$\.......$$.|.......$$$$$$\........$$$$$$$\.........$$$$$$\....................................................
.................................$$.._____|......$$..__$$\.......\$$\.$$..|......$$.|..$$.|......$$.|......$$..__$$\.......$$..__$$\.......$$..__$$\...................................................
.................................$$./............$$.|..$$.|.......\$$$$../.......$$.|..$$.|......$$.|......$$./..$$.|......$$.|..$$.|......$$./..$$.|..................................................
.................................$$.|............$$.|..$$.|.......$$..$$<........$$.|..$$.|......$$.|......$$.|..$$.|......$$.|..$$.|......$$.|..$$.|..................................................
.................................\$$$$$$$\.......$$.|..$$.|......$$../\$$\.......\$$$$$$..|......$$.|......\$$$$$$..|......$$.|..$$.|......\$$$$$$$.|..................................................
..................................\_______|......\__|..\__|......\__/..\__|.......\______/.......\__|.......\______/.......\__|..\__|.......\____$$.|..................................................
...........................................................................................................................................$$\...$$.|..................................................
...........................................................................................................................................\$$$$$$..|..................................................
...........................................................................................................................................\______/....................................................
.......................................................................................................................................................................................................
.......................................................................................................................................................................................................
.......................................................................................................................................................................................................
.....................................................................................................................................................................................................*/
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define LL long long
//freopen("xxx.in","r",stdin);
//freopen("xxx.out","w"	,stdout);
template<typename T>
inline T read(){
	T x=0;
	bool fg=0;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		fg|=(ch=='-');
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return fg?~x+1:x;
}