/*
By Ihor Menshykov, MIT license

g++ -lm -std=c++14 -include bits/stdc++.h -fsanitize=address -O3 sol.cpp -o sol &&
time ./sol < ./ins/a


g++ -lm -std=c++14 -include bits/stdc++.h -fsanitize=address -O3 sol.cpp -o sol &&
time python testing_tool.py ./sol

*/
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wregister"

// #include "defines.cpp"
#include <sys/time.h>
#include <bits/stdc++.h>	//	precompiled header that includes EVERYTHING
// #include <iostream>
// #include <vector>
// #include <math.h>	//	remember M_PIl and M_PI !
// #include <queue>	//	queue, priority_queue
// #include <string>
// #include <deque>
// #include <algorithm>
// #include <set>
// #include <bitset>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <random>
// #include <utility>
// #include <numeric>      // std::accumulate
// #include <tuple>
// #include <sstream>
// #include <stdlib.h>     /* srand, rand */
// #include <fstream>
// #include <ctime>        // std::time
// #include <time>        // std::time
// #include <chrono>
// #include <exception>
// #include <boost/filesystem.hpp>
// #include <sys/stat.h>
// #include <parallel/algorithm>
// #include <thread>
// #include <mutex>
// #include <future>

// #include "matplotlibcpp.h"
// #include "stat-vals.h"
// #include "stat-keys.h"
// namespace plt = matplotlibcpp;
using namespace std;



int		repeat_times			=	1;
float	randomization			=	0.;













//	Remember to use LONG_MAX , LLONG_MAX
#define		PRIME			919393
#define		LARGE_PRIME		2147483647 // Marsenne prime, also equal to INT_MAX //1234593421
#define		MIL				1000000
#define		BILL			(LL)1e9			
#define		BILLION			(LL)1e9			
#define		QUAN			(LL)1e18
#define		QUANTILLION		(LL)1e18
// #define		INT				__int128
#define		INT			(__int128)
#define		UINT			(unsigned __int128)

#define		LAZY_RND(to)					(	mt_rnd()%to			)	//	0 <= "LAZY" RND < to. May not be completely uniform
#define		RND_ONE_IN(x)					(	mt_rnd()%x == 0		)
#define		RND_CHANCE_IS(x)				(	zero_to_one_rnd(mt_rnd) < x	)
#define		RND_CHANCE						(	zero_to_one_rnd(mt_rnd)		)	//	0. <= RND_CHANCE <= 1.
#define		RAND_CHANCE						RND_CHANCE
#define		SHUFFLE(r)						shuffle( ALL(r) , mt_rnd);
#define		ASSERT(exp, msg)				assert(((void)msg, exp));

#define		N_ARGS_SEQ(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11,N,...)	N
#define		N_ARGS(...)						N_ARGS_SEQ(__VA_ARGS__, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
#define		CONCAT(a, b)					a ## b
#define		CONCAT_2(a, b)					CONCAT(a, b)

#define		A               				first
#define		B               				second
#define		ALL(a)							(a).begin(),(a).end()
#define		PAIR							make_pair
#define		PAIR_XX_X(a,b,c)				PAIR(PAIR(a,b),c)
#define		PAIR_X_XX(a,b,c)				PAIR(a,PAIR(b,c))
#define		PAIR_XX_XX(a,b,c,d)				PAIR(PAIR(a,b),PAIR(c,d))

#define		SIZE(x)							(int) x.size()
#define		SZ(x)							(int) x.size()
#define		EMT(x)							(0==x.size())
#define		PSZ(x)							(int) x->size()

#define		FROM_PII(p, x,y)				int x=p.A; int y=p.B;

#define		SORT(x)							sort( ALL(x) );					//	1 2 3 4
#define		SORT_SMALL_FIRST(x)				sort( ALL(x) );					//	1 2 3 4
#define		SORT_c(x,c)						sort( ALL(x), c );	//	c(a,b) = a<b  =>  1 2 3 4 ...  [true -> a first, false -> b first]

#define		PQ								priority_queue
#define		FL								(float)
#define		UMAP							unordered_map
#define		USET							unordered_set
#define		VI								vector<int>
#define		VL								vector<long>
#define		LL								long long
#define		LL_								(long long)
#define		LD								long double
#define		LD_								(long double)
#define		VLL								vector<long long>
#define		V128							vector<INT>
#define		VLD								vector<long double>
#define		VF								vector<float>
#define		VD								vector<double>
#define		VS								vector< string >
#define		VB								vector< bool >
#define		VVV(a)							vector< vector< vector< a > > >
#define		VVVV(a)							vector< vector< vector< vector< a > > > >
#define		VVVVV(a)						vector< vector< vector< vector< vector< a > > > > >
#define		VVL								vector< vector<long>	>
#define		VVLL							vector< vector<long long>	>
#define		VV128							vector< vector<INT>	>
#define		VVLD							vector< vector<long double>	>
#define		VVI								vector< vector<int>		>
#define		VVVI							vector< VVI		>
#define		VVVVI							vector< VVVI	>
#define		VVB								vector< VB		>
#define		VVVB							vector< VVB		>
#define		VVVVB							vector< VVVB	>
#define		VVF								vector< vector<float>	>
#define		VVD								vector< vector<double>	>
#define		VVS								vector< vector<string>	>
#define		P_FF							pair<float, float>
#define		VP_FF							vector<P_FF>
#define		VVP_FF							vector<vector<P_FF>>
#define		VVVP_FF							vector<vector<vector<P_FF>>>
#define		P_IF							pair<int, float>
#define		P_FI							pair<float,	int>
#define		P_DI							pair<double,	int>
#define		P_ID							pair<int, double>
#define		VP_IF							vector< pair<int,float> >
#define		VP_DI							vector< pair<double,int> >
#define		VP_ID							vector< pair<int,double> >
#define		VP_LDI							vector< pair<LD,int> >
#define		VP_ILD							vector< pair<int,LD> >
#define		VP_DD							vector< pair<double, double> >
#define		P_II							pair<int, int>
#define		P_II_I							pair<P_II	, int>
#define		P_I_II							pair<int	, P_II>
#define		VP_I_II							vector<  P_I_II >
#define		VVP_I_II						vector< VP_I_II >
#define		P_F_II							pair<float	, P_II>
#define		P_I_FI							pair<int	, P_FI>
#define		P_I_DI							pair<int	, P_DI>
#define		P_II_II							pair<P_II, P_II>
#define		P_DD							pair<double, double>
#define		VP_II							vector< pair<int,int> >
#define		VT_III							vector< tuple<int,int,int> >
#define		VP_FI							vector< pair<float,int> >
#define		VP_F_II							vector< P_F_II >
#define		VP_I_II							vector< P_I_II >
#define		VP_II_I							vector< P_II_I >
#define		VP_II_II						vector< P_II_II >
#define		VVP_FI							vector<  VP_FI	>
#define		VVP_II							vector<  VP_II	>
#define		VVVP_II							vector< VVP_II	>
#define		VVVVP_II						vector<VVVP_II	>
#define		P_LLLL							pair<long long, long long>
#define		VP_LLLL							vector<pair<long long, long long>>
#define		P_LL							pair<long, long>
#define		PUSH							push_back
#define		EMP								emplace_back
#define		C_SIZE(x)						(sizeof(x) / sizeof(x[0]))
#define		CLEAR(a)						memset(a, 0, sizeof(a));
#define		INF								2000000007
#define		PUSH_XF_FX(x,y)					push_back(PAIR(x,y))
#define		PUSH_X_XX(x,y,z)				push_back(PAIR( x , PAIR(y,z) ))
#define		PUSH_XX_X(x,y,z)				push_back(PAIR( PAIR(x,y) , z ))
#define		UNIQ(v)							unique( ALL(v) )
#define		ONLY_UNIQUE(v)					v.erase(	UNIQ(v) , v.end()  );	//	Removes consecutive same
#define		COPY_APPEND_TO(me,v)			{ me.resize(me.size() + v.size());	copy( ALL(v), me.end() -  v.size()); }
#define		APPEND_TO(me,v)					me.insert(	me.end()	, ALL(v) );
#define		APPEND_INTO_FROM_TO(me,v,f,t)	me.insert(	me.end()	, v.begin() + min(SIZE(v),f), v.begin() + min(SIZE(v),t) );
#define		ADD_BEFORE(me,v)				me.insert(	me.begin()	, ALL(v) );
#define		CLONE_A_TO_B(me,v)				{ v.resize(	me.size() );	copy(	ALL(me), v.begin() ); }
#define		CLONE_VV_A_TO_B(a,b)			{ b.resize(  a.size() );	F_all(i_224dk,b){  b[i_224dk].resize(	a[i_224dk].size() ); copy(	ALL(a[i_224dk]), b[i_224dk].begin() ); } }
#define		REMOVE_TILL(me,i)				{ me.erase( me.begin()		, me.begin() + i ); }
#define		REMOVE_AFTER(me,i)				{ me.erase( me.begin() + i	, me.end()		 ); }
#define		REMOVE_RANGE(me,f,t)			{ me.erase( me.begin() + f	, me.begin() + t ); }
#define		REMOVE_I(from,i)				{ from.erase( from.begin() + i ); }
#define		REMOVE_ITER(me,i)				{ me.erase( i ); }
#define		REMOVE_VALUE(me,v)				{ REMOVE_ITER(me, FIND(me,v) ); }
#define		REMOVE_FROM_SET(st,x)			{ st.erase( st.find(x) , st.end() ); }
#define		REVERSE(myvector)				reverse( ALL(myvector) );
#define		V_MAX_I(v)						distance(v.begin(), max_element( ALL(v) ))
#define		V_MIN_I(v)						distance(v.begin(), min_element( ALL(v) ))
#define		V_0(v)							v.resize(0);
#define		RESIZE_DOWN_TO(v,to)			v.resize( max(0, min(SZ(v), to)) );

#define		MINIMIZE(a,b)					a=min((a),(b));
#define		MAXIMIZE(a,b)					a=max((a),(b));
#define		UNCONDITIONAL_UPDATE_4(	best, nu,	best_id, nu_id)													{ best = (nu); best_id = (nu_id); }
#define		UNCONDITIONAL_UPDATE_6(	best, nu,	best_id, nu_id,		best_2, nu_2)								{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		UNCONDITIONAL_UPDATE_8(	best, nu,	best_id, nu_id,		best_2, nu_2,	best_3, nu_3)				{ best = (nu); best_id = (nu_id); best_2 = (nu_2); best_3 = (nu_3); }
#define		IF_LESS_UPDATE_4(		best, nu, 	best_id, nu_id)										if(nu < best) 											{ best = (nu); best_id = (nu_id); }
#define		IF_MORE_UPDATE_4(		best, nu, 	best_id, nu_id)										if(nu > best) 											{ best = (nu); best_id = (nu_id); }
#define		IF_LESS_UPDATE_6(		best, nu,	best_id, nu_id,		best_2, nu_2)					if(nu < best) 											{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		IF_LESS_UPDATE_8(		best, nu,	best_id, nu_id,		best_2, nu_2,	best_3, nu_3)	if(nu < best) 											{ best = (nu); best_id = (nu_id); best_2 = (nu_2); best_3 = (nu_3); }
#define		IF_MORE_UPDATE_6(		best, nu,	best_id, nu_id,		best_2, nu_2)					if(nu > best) 											{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		IF_MORE_UPDATE_8(		best, nu,	best_id, nu_id,		best_2, nu_2,	best_3, nu_3)	if(nu > best) 											{ best = (nu); best_id = (nu_id); best_2 = (nu_2); best_3 = (nu_3); }
#define		IF_LESS_EQ_UPDATE_4(	best, nu, 	best_id, nu_id)										if(	nu < best	||	 (nu	==	best) )					{ best = (nu); best_id = (nu_id); }
#define		IF_MORE_EQ_UPDATE_4(	best, nu, 	best_id, nu_id)										if(	nu > best	||	 (nu	==	best) )					{ best = (nu); best_id = (nu_id); }
#define		IF_LESS_EQ_UPDATE_6(	best, nu,	best_id, nu_id,		best_2, nu_2)					if(	nu < best	||	 (nu	==	best) )					{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		IF_MORE_EQ_UPDATE_6(	best, nu,	best_id, nu_id,		best_2, nu_2)					if(	nu > best	||	 (nu	==	best) )					{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		IF_LESS_EQ_RND_UPDATE_4(best, nu,	best_id, nu_id)										if(	nu < best	||	((nu	==	best) && (rand()%2)) )	{ best = (nu); best_id = (nu_id); }
#define		IF_MORE_EQ_RND_UPDATE_4(best, nu,	best_id, nu_id)										if(	nu > best	||	((nu	==	best) && (rand()%2)) )	{ best = (nu); best_id = (nu_id); }
#define		IF_LESS_EQ_RND_UPDATE_6(best, nu,	best_id, nu_id,		best_2, nu_2)					if(	nu < best	||	((nu	==	best) && (rand()%2)) )	{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		IF_MORE_EQ_RND_UPDATE_6(best, nu,	best_id, nu_id,		best_2, nu_2)					if(	nu > best	||	((nu	==	best) && (rand()%2)) )	{ best = (nu); best_id = (nu_id); best_2 = (nu_2); }
#define		IF_THEN_UPDATE_3 (cond,				best_id, nu_id)										if(	cond )												{ 			   best_id = (nu_id); }
#define		IF_THEN_UPDATE_7(cond,	best, nu,	best_id, nu_id,		best_2, nu_2)					if(	cond )												{ 			   best_id = (nu_id); best_2 = (nu_2); }
// #define		IF_THEN_UPDATE_3(cond,	best, nu,	best_id, nu_id,		best_2, nu_2)					if(	cond )												{ best = nu; best_id = nu_id; best_2 = nu_2; }

#define		UNCONDITIONAL_UPDATE(...)		CONCAT_2(UNCONDITIONAL_UPDATE_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_LESS_UPDATE(...)				CONCAT_2(IF_LESS_UPDATE_,		N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_MORE_UPDATE(...)				CONCAT_2(IF_MORE_UPDATE_,		N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_MORE_EQ_UPDATE(...)			CONCAT_2(IF_MORE_EQ_UPDATE_,	N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_LESS_EQ_UPDATE(...)			CONCAT_2(IF_LESS_EQ_UPDATE_,	N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_LESS_EQ_RND_UPDATE(...)		CONCAT_2(IF_LESS_EQ_RND_UPDATE_,N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_MORE_EQ_RND_UPDATE(...)		CONCAT_2(IF_MORE_EQ_RND_UPDATE_,N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IF_THEN_UPDATE(...)				CONCAT_2(IF_THEN_UPDATE_,N_ARGS(__VA_ARGS__))(__VA_ARGS__)

// #define		F(i,n)							for (int i = 0; i < n; ++i)
#define		F_step(i,t,st)					for (int i = 0; i < t; i+=st )
#define		F_from_step(i,f,t,st)			for (int i = f; i < t; i+=st)
#define		F_all(i,n)						for (int i = 0; i < SIZE(n);	++i)
// #define		F_all_elem(i,e,n)				auto e=n[0]; for (int i = 0; i < SIZE(n);	++i, e=n[i])
// #define		F_all_except_last(i,n)			for (int i = 0; i < SIZE(n)-1;	++i)
// #define		F_all_rev(i,n)					for (int i = SIZE(n)-1; i >= 0; --i)
// #define		F_rev(i,n)						for (int i = n-1; i >= 0; --i)
// #define		F_rev_till(i,till,n)			for (int i = n-1; i >= till; --i)
#define		F_from(i,f,t)					for (auto i = f; i < t; ++i)
// #define		F_from_till(i,f,t)				for (auto i = f; i != t; f<t? i++ : i--)
#define		F_elem(e,v)						for (auto &e : v)
#define		F_in(it,v)						for (auto it = v.begin() ; it != v.end(); ++it)

#define		F(n,i)							for (int i = 0; i < (n);		++i)		{
#define		F_S_I(n,s,i)					for (int i = 0; i < (n);		i+=s)		{
#define		F_WHERE(n,i,c)					for (int i = 0; i < n; ++i)		if(c)	{

// #define		FTSI(f,t,s,i)					for (int i = f; i != t;			--i)		{
#define		F_REV(n,i)						for (int i = n-1; i >= 0;		--i)		{
// #define		F_F_T_DOWN(n,t,i)				for (int i = (n); i >= (t);		--i)		{
#define		F_FROM(n,i,f)					for (int i = f; i < (n);		++i)		{

#define		F_I_F_T(i,f,t)					for (int i = f; (f<t && i<=t)  ||  (f>=t && i>=t);	f<t ? ++i : --i)			{
#define		F_I_F_T_UP(i,f,t)				for (int i = f; i<=t;	++i		)			{
#define		F_I_F_T_DOWN(i,f,t)				for (int i = f; i>=t;	--i		)			{
#define		F_I_F_T_S_UP(i,f,t,step)		for (int i = f; i<=t;	i+=step	)			{
#define		F_I_F_T_S_DOWN(i,f,t,step)		for (int i = f; i>=t;	i-=step	)			{
#define		F_I_F_T_W(i,f,t,w)				for (int i = f; f<t ? i<=t  :  i>=t;	f<t ? ++i : --i)	if(w)	{

#define		F_I(v,i)						for (int i = 0; i < SIZE(v);	++i)		{
#define		F_I_REV(v,i)					for (int i = SIZE(v)-1; i >= 0; --i)		{
#define		F_I_FROM(v,i,f)					for (int i = f; i < SIZE(v);	++i)		{

#define		F_I_E_F(v,i,e,f)				for (int i = f; i < SIZE(v);	++i)						{	auto	&e=v[i];
#define		F_I_E_F_T(v,i,e,f,t)			for (int i = f; f<t ? i<=t  :  i>=t;	f<t ? ++i : --i)	{	auto	&e=v[i];
#define		F_I_E_W(v,i,e,w)				for (int i = 0; i < SIZE(v);	++i) if(w)					{	auto	&e=v[i];
#define		F_I_E(v,i,e)					for (int i = 0; i < SIZE(v);	++i)						{	auto	&e=v[i];
#define		F_I_E_F(v,i,e,f)				for (int i = f; i < SIZE(v);	++i)						{	auto	&e=v[i];
#define		F_I_E_F_T(v,i,e,f,t)			for (int i = f; f<t ? i<=t  :  i>=t;	f<t ? ++i : --i)	{	auto	&e=v[i];
#define		F_I_E_TO_MINUS(v,i,e,l)			for (int i = 0; i < SIZE(v)-l;	++i)						{	auto	&e=v[i];
#define		F_I_E_TO(v,i,e,t)				for (int i = 0; i < t;			++i)						{	auto	&e=v[i];
#define		F_I_E_REV(v,i,e)				for (int i = SIZE(v)-1; i >= 0;	--i)						{	auto	&e=v[i];
#define		F_I_E_REV_WHERE(v,i,e,w)		for (int i = SIZE(v)-1; i >= 0;	--i) if(w)					{	auto	&e=v[i];
#define		F_I_E_REV_FROM(v,i,e,s)			for (int i = s; 		i >= 0;	--i) 						{	auto	&e=v[i];

#define		F_I_E_RANDOM(v,i,e,r)			RANGE(r,0,SZ(v)-1); SHUFFLE(r);  for (auto &i : r)			{	auto	&e=v[i];

#define		F_I_PE(v,i,ea,eb)				for (int i = 0; i < SIZE(v);	++i)		{	auto	&ea=v[i].A;		auto  &eb=v[i].B;
#define		F_I_PE_F(v,i,ea,eb,f)			for (int i = f; i < SIZE(v);	++i)		{	auto	&ea=v[i].A;		auto  &eb=v[i].B;

#define		F_VI(val,e)					 	for (auto &e : VI val)					{
#define		F_E(v,e)						for (auto &e : v)						{
#define		F_E_WHERE(v,e,w)				for (auto &e : v)				if(w)	{

#define		F_I_T_SHUFFLED_RANGE(i,t,r)		RANGE(r,0,t); SHUFFLE(r) F_elem(i,r)  //PARTIAL_RAND_RANGE(r,0,t,1) F_elem(i,r)

// #define		F_where(i,n,c)					for (int i = 0; i < n; ++i)									if(c)
// #define		F_step_where(i,t,st,c)			for (int i = 0; i < t; i+=st )								if(c)
// #define		F_from_step_where(i,f,t,st,c)	for (int i = f; i < t; i+=st)								if(c)
// #define		F_all_where(i,n,c)				for (int i = 0; i < SIZE(n);	++i)						if(c)
// #define		F_all_elem_where(i,e,n,c)		auto e=n[i];	for (int i = 0; i < SIZE(n);	++i)		if(c)
// #define		F_all_except_last_where(i,n,c)	for (int i = 0; i < SIZE(n)-1;	++i)						if(c)
// #define		F_all_rev_where(i,n,c)			for (int i = SIZE(n)-1; i >= 0; --i)						if(c)
// #define		F_rev_where(i,n,c)				for (int i = n-1; i >= 0; --i)								if(c)
// #define		F_rev_till_where(i,till,n,c)	for (int i = n-1; i >= till; --i)							if(c)
// #define		F_from_where(i,f,t,c)			for (auto i = f; i < t; ++i)								if(c)
// #define		F_from_till_where(i,f,t,c)		for (auto i = f; i != t; f<t? i++ : i--)					if(c)
// #define		F_elem_where(e,v,c)				for (auto &e : v)											if(c)
// #define		F_iter_where(it,v,c)			for (auto it = v.begin()	; it != v.end(); ++it)			if(c)
// #define		F_iter_rev_where(it,v,c)		for (auto it = v.rbegin()	; it != v.rend(); ++it)			if(c)
// #define		F_iter_rev(it,v)				for (auto it = v.rbegin()	; it != v.rend(); ++it)

#define		RANGE(rng,f,t)					VI rng(t-f); F_from(i_3483,f,t){ rng[i_3483]	=	i_3483; }
// #define		ZERO_PLUS(x)					max(0, x)

#define		BIN_SEARCH(v,val)				binary_search( ALL(v), val )
#define		BIN_SEARCH_c(v,val,c)			binary_search( ALL(v), val, c )
#define		UP_BOUND_I(V,val)				upper_bound( ALL(V) ,val )    - V.begin()
#define		LOW_BOUND_I(V,val)				lower_bound( ALL(V) ,val )    - V.begin()
#define		UP_BOUND_I_c(V,val,c)			upper_bound( ALL(V) ,val, c ) - V.begin()
#define		LOW_BOUND_I_c(V,val,c)			lower_bound( ALL(V) ,val, c ) - V.begin()
#define		FIND(me,val)					find( ALL(me), val )
#define		FIND_I(set_,val)				FIND(set_,val)  -  set_.begin() 
#define		THIS_EL_INSIDE(k,set_)			set_.find( k ) != set_.end()
#define		THIS_EL_NOT_INSIDE(k,set_)		set_.find( k ) == set_.end()
#define		IF_THIS_EL_INSIDE(k,set_)		if(  set_.find( k ) != set_.end()  )
#define		IF_THIS_EL_NOT_INSIDE(k,set_)	if(  set_.find( k ) == set_.end()  )

#define		THIS_EL_INSIDE_V(e,v)			find( ALL(v) , e ) != v.end()
#define		THIS_EL_NOT_INSIDE_V(e,v)		find( ALL(v) , e ) == v.end()
#define		IF_THIS_EL_INSIDE_V(e,v)		if(  find( ALL(v) , e ) != v.end()  )
#define		IF_THIS_EL_NOT_INSIDE_V(e,v)	if(  find( ALL(v) , e ) == v.end()  )

#define		FILL(me,v)						fill(me.begin(), me.end(), v);
#define		ZERO(me)						FILL(me, 0);
#define		BAR_VI_FROM_MAP(vi,m)			VI vi; F(i, (*m.rbegin()).A +1 ){vi.PUSH( m[i] ); }  plt::figure_size(1920*2/3, 1080*2/3);  plt::bar( vi );
#define		BAR_FROM_MAP(m)					VI vi; F(i, (*m.rbegin()).A +1 ){vi.PUSH( m[i] ); }  plt::figure_size(1920*2/3, 1080*2/3);  plt::bar( vi );
#define		SAVE_BAR_FROM_MAP_AS(m,name)	VI vi; F(i, (*m.rbegin()).A +1 ){vi.PUSH( m[i] ); }  plt::figure_size(1920*2/3, 1080*2/3);  plt::bar( vi );	plt::save( name );
#define		BAR_FROM_VI(vi)					plt::figure_size(1920*2/3, 1080*2/3);  plt::bar( vi );
#define		SAVE_BAR_FROM_VI_AS(vi,name)	plt::figure_size(1920*2/3, 1080*2/3);  plt::bar( vi );	plt::save( name );
#define		CLOCK_TIME_S(f,t)				(t 		 - f) / (double)CLOCKS_PER_SEC
#define		CLOCK_TIME_SINCE(f)				(clock() - f) / (double)CLOCKS_PER_SEC

#define		TIME(now)						gettimeofday(&now, NULL);
#define		TIME_NOW(now)					struct timeval now; gettimeofday(&now, NULL);


#define		STR(a)			to_string(a)
#define		CHAR_STR(a)		string(1,a)
#define		COL_BLK		((string)"\033[30m" )
#define		COL_R		((string)"\033[31;1m" )
#define		COL_R_BG	((string)"\033[41m" ) + COL_BLK
#define		COL_G		((string)"\033[32;1m" )
#define		COL_G_BG	((string)"\033[42m" ) + COL_BLK
#define		COL_B		((string)"\033[34;1m" )
#define		COL_B_BG	((string)"\033[44m" )
#define		COL_Y		((string)"\033[93m" )
#define		COL_Y_BG	((string)"\033[43m" ) + COL_BLK
#define		COL_M		((string)"\033[35;1m" )	//magenta
#define		COL_M_BG	((string)"\033[45m" )	
#define		COL_C		((string)"\033[36;1m" )	//cyan
#define		COL_C_BG	((string)"\033[46m" )	
#define		COL_END		((string)"\033[0m" )


#define		END								std::endl
#define		OUTnl							{std::cout	<<	COL_END << endl;}	//	new line
#define		OUT_LINE						{std::cout	<<	endl;}				//	new line
#define		OUT_1(x)						{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END	<< endl;}
#define		OUT_2(x,y)						{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<< 	COL_END<< endl;}
#define		OUT_3(x,y,z)					{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END	<<	endl;}
#define		OUT_4(x,y,z,k)					{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END	<<	endl;}
#define		OUT_5(x,y,z,k,l)				{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END	<<	endl;}
#define		OUT_6(x,y,z,k,l,u)				{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END	<<	endl;}
#define		OUT_7(x,y,z,k,l,u,p)			{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END	<<	endl;}
#define		OUT_8(x,y,z,k,l,u,p,h)			{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END	<<	endl;}
#define		OUT_9(x,y,z,k,l,u,p,h,b)		{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END+"	"	<<	b	<<	COL_END	<<	endl;}
#define		OUT_10(x,y,z,k,l,u,p,h,b,m)		{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END+"	"	<<	b	<<	COL_END+"	"	<<	m	<<	COL_END	<<	endl;}
#define		OUT_11(x,y,z,k,l,u,p,h,b,m,w)	{std::cout	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END+"	"	<<	b	<<	COL_END+"	"	<<	m	<<	COL_END+"	"	<<	w	<<	COL_END	<<	endl;}
#define		COUT_1(x)						{std::cout	<<	x	<<	endl;}
#define		COUT_2(x,y)						{std::cout	<<	x	<<	" "	<<	y	<< endl;}
#define		COUT_3(x,y,z)					{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	endl;}
#define		COUT_4(x,y,z,k)					{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	endl;}
#define		COUT_5(x,y,z,k,l)				{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	" "	<<	l	<<	endl;}
#define		COUT_6(x,y,z,k,l,u)				{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	" "	<<	l	<<	" "	<<	u	<<	endl;}
#define		COUT_7(x,y,z,k,l,u,p)			{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	" "	<<	l	<<	" "	<<	u	<<	" "	<<	p	<<	endl;}
#define		COUT_8(x,y,z,k,l,u,p,h)			{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	" "	<<	l	<<	" "	<<	u	<<	" "	<<	p	<<	" "	<<	h	<<	endl;}
#define		COUT_9(x,y,z,k,l,u,p,h,b)		{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	" "	<<	l	<<	" "	<<	u	<<	" "	<<	p	<<	" "	<<	h	<<	" "	<<	b	<<	endl;}
#define		COUT_10(x,y,z,k,l,u,p,h,b,m)	{std::cout	<<	x	<<	" "	<<	y	<<	" "	<<	z	<<	" "	<<	k	<<	" "	<<	l	<<	" "	<<	u	<<	" "	<<	p	<<	" "	<<	h	<<	" "	<<	b	<<	" "	<<	m	<<	endl;}
#define		CERR_1(x)						{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END	<< endl;}
#define		CERR_2(x,y)						{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<< 	COL_END<< endl;}
#define		CERR_3(x,y,z)					{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END	<<	endl;}
#define		CERR_4(x,y,z,k)					{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END	<<	endl;}
#define		CERR_5(x,y,z,k,l)				{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END	<<	endl;}
#define		CERR_6(x,y,z,k,l,u)				{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END	<<	endl;}
#define		CERR_7(x,y,z,k,l,u,p)			{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END	<<	endl;}
#define		CERR_8(x,y,z,k,l,u,p,h)			{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END	<<	endl;}
#define		CERR_9(x,y,z,k,l,u,p,h,b)		{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END+"	"	<<	b	<<	COL_END	<<	endl;}
#define		CERR_10(x,y,z,k,l,u,p,h,b,m)	{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END+"	"	<<	b	<<	COL_END+"	"	<<	m	<<	COL_END	<<	endl;}
#define		CERR_11(x,y,z,k,l,u,p,h,b,m,w)	{std::cerr	<<	COL_END+(string)"	"	<<	x	<<	COL_END+"	"	<<	y	<<	COL_END+"	"	<<	z	<<	COL_END+"	"	<<	k	<<	COL_END+"	"	<<	l	<<	COL_END+"	"	<<	u	<<	COL_END+"	"	<<	p	<<	COL_END+"	"	<<	h	<<	COL_END+"	"	<<	b	<<	COL_END+"	"	<<	m	<<	COL_END+"	"	<<	w	<<	COL_END	<<	endl;}

#define		CERRY_1(x)						{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	COL_END	<< endl;}
#define		CERRY_2(x,y)					{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<< 	COL_END<< endl;}
#define		CERRY_3(x,y,z)					{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	COL_END	<<	endl;}
#define		CERRY_4(x,y,z,k)				{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	COL_END	<<	endl;}
#define		CERRY_5(x,y,z,k,l)				{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	COL_END	<<	endl;}
#define		CERRY_6(x,y,z,k,l,u)			{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	"	"	<<	u	<<	COL_END	<<	endl;}
#define		CERRY_7(x,y,z,k,l,u,p)			{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	"	"	<<	u	<<	"	"	<<	p	<<	COL_END	<<	endl;}
#define		CERRY_8(x,y,z,k,l,u,p,h)		{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	"	"	<<	u	<<	"	"	<<	p	<<	"	"	<<	h	<<	COL_END	<<	endl;}
#define		CERRY_9(x,y,z,k,l,u,p,h,b)		{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	"	"	<<	u	<<	"	"	<<	p	<<	"	"	<<	h	<<	"	"	<<	b	<<	COL_END	<<	endl;}
#define		CERRY_10(x,y,z,k,l,u,p,h,b,m)	{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	"	"	<<	u	<<	"	"	<<	p	<<	"	"	<<	h	<<	"	"	<<	b	<<	"	"	<<	m	<<	COL_END	<<	endl;}
#define		CERRY_11(x,y,z,k,l,u,p,h,b,m,w)	{std::cerr	<<	COL_END+COL_Y+(string)"	"	<<	x	<<	"	"	<<	y	<<	"	"	<<	z	<<	"	"	<<	k	<<	"	"	<<	l	<<	"	"	<<	u	<<	"	"	<<	p	<<	"	"	<<	h	<<	"	"	<<	b	<<	"	"	<<	m	<<	"	"	<<	w	<<	COL_END	<<	endl;}

#define		OUT(...)					CONCAT_2(OUT_ , N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		COUT(...)					CONCAT_2(COUT_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CERR(...)					CONCAT_2(CERR_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CERRY(...)					CONCAT_2(CERRY_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		OUT_map(m)					F_elem(e, m ){ OUT_2( e.A, e.B  )}
#define		OUT_MATRIX(m)				{	F_all(i_22d,m){cout<<i_22d<<"	";	F_all(j_3da, m[i_22d] ){cout<<m[i_22d][j_3da]<<" ";}	OUT_LINE	} }
#define		OUT_P(i)					std::cout<<i.A<<" "<<i.B<<END;
#define		CaseOUT(tt,...)				COUT("Case #" + STR(tt) + ":"	,	__VA_ARGS__)
#define		CaseOUT_empty(tt)				COUT("Case #" + STR(tt) + ":")

#define		SET_COUT_PRECISION(v)				cout.precision(v);
#define		SET_COUT_FIX_PRECISION				cout.setf( std::ios::fixed, std:: ios::floatfield );
#define		SET_FAKE_INPUT_STORE_TRUE(s,t)		t=cout.rdbuf();	istringstream fake_iss(s);	cin.rdbuf( fake_iss.rdbuf());
#define		SET_FAKE_INPUT(s)					istringstream fake_iss(s);	cin.rdbuf(fake_iss.rdbuf());
#define		SET_TRUE_INPUT(input)				cin.rdbuf(input);

#define		CIN_S(i)				string		i;			std::cin>>i;
#define		CIN_P1(i)				P_II		i;			std::cin>>i.A>>i.B;
#define		CIN_P2(i)				P_II		i,j;		std::cin>>i.A>>i.B>>j.A>>j.B;
#define		CIN_LL1(i)				long long	i;			std::cin>>i;
#define		CIN_LL2(i,j)			long long	i,j;		std::cin>>i>>j;
#define		CIN_LL3(i,j,k)			long long	i,j,k;		std::cin>>i>>j>>k;
#define		CIN_LL4(i,j,k,x)		long long	i,j,k,x;	std::cin>>i>>j>>k>>x;
#define		CIN_I1(i)				int			i;			std::cin>>i;
#define		CIN_I2(i,j)				int			i,j;		std::cin>>i>>j;
#define		CIN_I3(i,j,k)			int			i,j,k;		std::cin>>i>>j>>k;
#define		CIN_I4(i,j,k,x)			int			i,j,k,x;	std::cin>>i>>j>>k>>x;
#define		CIN_F1(i)				float		i;			std::cin>>i;
#define		CIN_F2(i,j)				float		i,j;		std::cin>>i>>j;
#define		CIN_F3(i,j,k)			float		i,j,k;		std::cin>>i>>j>>k;
#define		CIN_F4(i,j,k,x)			float		i,j,k,x;	std::cin>>i>>j>>k>>x;
#define		CIN_D1(i)				double		i;			std::cin>>i;
#define		CIN_D2(i,j)				double		i,j;		std::cin>>i>>j;
#define		CIN_D3(i,j,k)			double		i,j,k;		std::cin>>i>>j>>k;
#define		CIN_D4(i,j,k,x)			double		i,j,k,x;	std::cin>>i>>j>>k>>x;
#define		CIN_1(i)				cin>>i;
#define		CIN_2(i,j)				cin>>i>>j;
#define		CIN_3(i,j,k)			cin>>i>>j>>k;
#define		CIN_4(i,j,k,x)			cin>>i>>j>>k>>x;
#define		CIN_5(i,j,k,x,o)		cin>>i>>j>>k>>x>>o;



#define		IN_LL_1(i)				long long	i;			infile>>i;
#define		IN_LL_2(i,j)			long long	i,j;		infile>>i>>j;
#define		IN_LL_3(i,j,k)			long long	i,j,k;		infile>>i>>j>>k;
#define		IN_LL_4(i,j,k,x)		long long	i,j,k,x;	infile>>i>>j>>k>>x;
#define		IN_S_1(i)				string		i;			infile>>i;
#define		IN_S_2(i)				string		i,j;		infile>>i>>j;
#define		IN_S_3(i)				string		i,j,k;		infile>>i>>j>>k;
#define		IN_S_4(i)				string		i,j,k,x;	infile>>i>>j>>k>>x;
#define		IN_P_1(i)				P_II		i;			infile>>i.A>>i.B;
#define		IN_P_2(i,j)				P_II		i,j;		infile>>i.A>>i.B>>j.A>>j.B;
#define		IN_I_1(i)				int			i;			infile>>i;
#define		IN_I_2(i,j)				int			i,j;		infile>>i>>j;
#define		IN_I_3(i,j,k)			int			i,j,k;		infile>>i>>j>>k;
#define		IN_I_4(i,j,k,x)			int			i,j,k,x;	infile>>i>>j>>k>>x;
#define		IN_D_1(i)				double		i;			infile>>i;
#define		IN_D_2(i,j)				double		i,j;		infile>>i>>j;
#define		IN_D_3(i,j,k)			double		i,j,k;		infile>>i>>j>>k;
#define		IN_D_4(i,j,k,x)			double		i,j,k,x;	infile>>i>>j>>k>>x;
#define		IN_F_1(i)				float		i;			infile>>i;
#define		IN_F_2(i,j)				float		i,j;		infile>>i>>j;
#define		IN_F_3(i,j,k)			float		i,j,k;		infile>>i>>j>>k;
#define		IN_F_4(i,j,k,x)			float		i,j,k,x;	infile>>i>>j>>k>>x;

#define		IN_1(i)					infile>>i;
#define		IN_2(i,j)				infile>>i>>j;
#define		IN_3(i,j,k)				infile>>i>>j>>k;
#define		IN_4(i,j,k,x)			infile>>i>>j>>k>>x;
#define		IN_5(i,j,k,x,o)			infile>>i>>j>>k>>x>>o;

#define		IN_I_PUSH(a)			{IN_I(g2341)	a.PUSH(g2341);}
#define		IN_S_PUSH(a)			{IN_S(g2341)	a.PUSH(g2341);}
#define		IN_F_PUSH(a)			{IN_F(g2341)	a.PUSH(g2341);}
#define		IN_P_PUSH(a)			{IN_P(g2341)	a.PUSH(g2341);}

#define		FOUT_P(i)				outf<<i.A<<" "<<i.B<<END;
#define		FOUT_1(i)				outf<<i<<END;
#define		FOUT_2(i,j)				outf<<i<<" "<<j<<END;
#define		FOUT_3(i,j,k)			outf<<i<<" "<<j<<" "<<k<<END;
#define		FOUT_4(i,j,k,x)			outf<<i<<" "<<j<<" "<<k<<" "<<x<<END;
#define		FOUT_5(i,j,k,x,y)		outf<<i<<" "<<j<<" "<<k<<" "<<x<<" "<<y<<END;
#define		FOUT_6(i,j,k,x,y,z)		outf<<i<<" "<<j<<" "<<k<<" "<<x<<" "<<y<<" "<<z<<END;
#define		FOUT_map(m)				F_elem(e, m ){ FOUT_2( e.A, e.B  )}

#define		FOUT(...)				CONCAT_2(FOUT_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CIN_I(...)				CONCAT_2(CIN_I, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CIN_LL(...)				CONCAT_2(CIN_LL, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CIN_F(...)				CONCAT_2(CIN_F, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CIN_D(...)				CONCAT_2(CIN_D, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		CIN(...)				CONCAT_2(CIN_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN(...)					CONCAT_2(IN_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN_I(...)				CONCAT_2(IN_I_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN_LL(...)				CONCAT_2(IN_LL_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN_D(...)				CONCAT_2(IN_D_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN_F(...)				CONCAT_2(IN_F_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN_P(...)				CONCAT_2(IN_P_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		IN_S(...)				CONCAT_2(IN_S_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)


// ARRAYS NEED TO BE SORTED FIRST
#define		UNION_A_B_TO(a,b,to)		set_union		(ALL(a),ALL(b),back_inserter(to));
#define		INTERSECTION_A_B_TO(a,b,to)	set_intersection(ALL(a),ALL(b),back_inserter(to));

#define		SUM_VI(v)				accumulate( v.begin(), v.end(), 0LL) 
#define		SUM_VF(v)				accumulate( v.begin(), v.end(), 0.)
#define		F_AVG_VI(v)				(float) SUM_VI(v)	/	(float) v.size()
#define		F_AVG_VF(v)				SUM_VF(v)			/	(double) v.size()
#define		MEDIAN(v,m)				auto prtly_srtd = v; nth_element(prtly_srtd.begin(), prtly_srtd.begin() + prtly_srtd.size()/2, prtly_srtd.end()); auto m = v[v.size()/2];

#define		ADD_TO_V(v,by)			{ F_all(i_9dx, v){ v[i_9dx]+=by; } }
#define		SUBTRACT_FROM_V(v,by)	{ F_all(i_9dx, v){ v[i_9dx]-=by; } }
#define		MULTIPLY_V_BY(v,by)		{ F_all(i_9dx, v){ v[i_9dx]*=by; } }
#define		DIVIDE_V_BY(v,by)		{ long double by_rev	= (long double)1./(long double)by;	MULTIPLY_V_BY(v,by_rev) }

#define		ADD_TO_VV(v,by)			{ F_all(j_4dx, v){ ADD_TO_V			(v[j_4dx] , by); } }
#define		SUBTRACT_FROM_VV(v,by)	{ F_all(j_4dx, v){ SUBTRACT_FROM_V	(v[j_4dx] , by); } }
#define		MULTIPLY_VV_BY(v,by)	{ F_all(j_4dx, v){ MULTIPLY_V_BY	(v[j_4dx] , by); } }
#define		DIVIDE_VV_BY(v,by)		{ long double by_rev_x = (long double)1./(long double)by;	MULTIPLY_VV_BY(v,by_rev_x) }

#define		ADD_V(v,b)				{ F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]+=b[i_94kd]; } }
#define		SUBTRACT_V(v,b)			{ F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]-=b[i_94kd]; } }
#define		MULTIPLY_V(v,b)			{ F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]*=b[i_94kd]; } }
#define		DIVIDE_BY_V(v,b)		{ F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd]/=b[i_94kd]; } }
#define		DIVIDE_BY_V_LD(v,b)		{ F(i_94kd, min( SIZE(v) , SIZE(b) ) ){ v[i_94kd] =(long double)v[i_94kd] / (long double)b[i_94kd]; } }
#define		ADD_VV(v,b)				{ F(i_4857, min( SIZE(v) , SIZE(b) ) ){ ADD_V			(v[i_4857] , b[i_4857]) } }
#define		SUBTRACT_VV(v,b)		{ F(i_4857, min( SIZE(v) , SIZE(b) ) ){ SUBTRACT_V		(v[i_4857] , b[i_4857]) } }
#define		MULTIPLY_VV(v,b)		{ F(i_4857, min( SIZE(v) , SIZE(b) ) ){ MULTIPLY_V		(v[i_4857] , b[i_4857]) } }
#define		DIVIDE_BY_VV(v,b)		{ F(i_4857, min( SIZE(v) , SIZE(b) ) ){ DIVIDE_BY_V		(v[i_4857] , b[i_4857]) } }
#define		DIVIDE_BY_VV_LD(v,b)	{ F(i_4857, min( SIZE(v) , SIZE(b) ) ){ DIVIDE_BY_V_LD	(v[i_4857] , b[i_4857]) } }

#define		NORMALIZE_VF(v)				{ float	 mul = 1./( *max_element(ALL(v)) );	MULTIPLY_ALL_BY(v,mul) }
#define		NORMALIZE_VD(v)				{ double mul = 1./( *max_element(ALL(v)) );	MULTIPLY_ALL_BY(v,mul) }
#define		PERCENTAGES_OF_SUM_VF(v)	{ float	 mul = 1./( SUM_VF(v) );			MULTIPLY_ALL_BY(v,mul) }
#define		PERCENTAGES_OF_SUM_VD(v)	{ double mul = 1./( SUM_VF(v) );			MULTIPLY_ALL_BY(v,mul) }

#define		MIN_MAX(a,b)					{if (a > b) swap(a,b);}

#define		MAX_2(a,b,c)					max(a		 , b)
#define		MAX_3(a,b,c)					max(a		 , max(b,c))
#define		MAX_4(a,b,c,d)					max(max(a,d) , max(b,c))
#define		MAX_5(a,b,c,d,e)				max(max(a,d) , MAX_3(b,c,e))
#define		MAX_6(a,b,c,d,e,f)				max(max(a,b) , MAX_4(c,d,e,f))
#define		MIN_2(a,b,c)					min(a		 , b)
#define		MIN_3(a,b,c)					min(a		 , min(b,c))
#define		MIN_4(a,b,c,d)					min(min(a,d) , min(b,c))
#define		MIN_5(a,b,c,d,e)				min(min(a,b) , MAX_3(c,d,e))
#define		MIN_6(a,b,c,d,e,f)				min(min(a,b) , MAX_4(c,d,e,f))
#define		MAX(...)						CONCAT_2(MAX_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)
#define		MIN(...)						CONCAT_2(MIN_, N_ARGS(__VA_ARGS__))(__VA_ARGS__)

#define		POW_2(x)		(x*x)
#define		POW_3(x)		(x*x*x)





#define ARGS_SIZE_(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,size,...) size
#define ARGS_SIZE(...) ARGS_SIZE_(__VA_ARGS__,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1)
 
#define DB_1(x) #x << "=" << (x) <<
#define DB_2(x, ...) #x << "=" << (x) << ", " << DB_1(__VA_ARGS__)
#define DB_3(x, ...) #x << "=" << (x) << ", " << DB_2(__VA_ARGS__)
#define DB_4(x, ...) #x << "=" << (x) << ", " << DB_3(__VA_ARGS__)
#define DB_5(x, ...) #x << "=" << (x) << ", " << DB_4(__VA_ARGS__)
#define DB_6(x, ...) #x << "=" << (x) << ", " << DB_5(__VA_ARGS__)
#define DB_7(x, ...) #x << "=" << (x) << ", " << DB_6(__VA_ARGS__)
#define DB_8(x, ...) #x << "=" << (x) << ", " << DB_7(__VA_ARGS__)
#define DB_9(x, ...) #x << "=" << (x) << ", " << DB_8(__VA_ARGS__)
#define DB_10(x, ...) #x << "=" << (x) << ", " << DB_9(__VA_ARGS__)
#define DB_11(x, ...) #x << "=" << (x) << ", " << DB_10(__VA_ARGS__)
#define DB_12(x, ...) #x << "=" << (x) << ", " << DB_11(__VA_ARGS__)
#define DB_13(x, ...) #x << "=" << (x) << ", " << DB_12(__VA_ARGS__)
#define DB_14(x, ...) #x << "=" << (x) << ", " << DB_13(__VA_ARGS__)
#define DB_15(x, ...) #x << "=" << (x) << ", " << DB_14(__VA_ARGS__)
#define DB__(size, ...) DB_##size(__VA_ARGS__)
#define DB_(size, ...) DB__(size, __VA_ARGS__)
 
#ifdef BZ
#define DB(...) do {cerr << DB_(ARGS_SIZE(__VA_ARGS__), __VA_ARGS__) endl;} while (0);
#else
#define DB(...) ;
#endif






								struct timeval time_start;
								inline double		TIME_SINCE(struct timeval back_then)
									{
									struct timeval now; gettimeofday(&now, NULL);
									return	((now.tv_sec  - back_then.tv_sec) * 1000000u + 
											now.tv_usec - back_then.tv_usec) / 1.e6;
									}

								random_device rndd; 
								mt19937 mt_rnd(rndd());
								uniform_real_distribution<> zero_to_one_rnd(0.0, 1.0);


								template <class T>
								void SORT_LARGE_FIRST(vector<T> &v) 
									{
									sort( ALL(v), greater<T>());
									}

								template <class T>
								vector<T> Shuffled_Per_Indices( vector<T> &v, vector<int> &ind )
									{
									vector<T> nu(
												min( SIZE(v), SIZE(ind) ) 
												);
									F_all(i, nu)
										{
										nu	=	v[ ind[i] ];
										}
									return nu;
									}

								template <class T, class U>
								vector<T> Split_Pair_0( vector< pair<T,U> > &v )
									{
									vector<T> nu( SIZE(v) );
									F_all(i,v)
										{
										nu[i]	=	v[i].A;
										}
									return	nu;
									}

								template <class T, class U>
								vector<U> Split_Pair_1( vector< pair<T,U> > &v )
									{
									vector<U> nu( SIZE(v) );
									F_all(i,v)
										{
										nu[i]	=	v[i].B;
										}
									return	nu;
									}

								template <class T, class U>
								vector<T> Split_Tuple( vector< tuple<T,U> > &v , int x )	//	x = 0, 1, etc
									{
									vector<T> nu( SIZE(v) );
									F_all(i,v)
										{
										nu[i]	=	std::get<x>( v[i] );
										}
									return	nu;
									}

								template <class T>
								vector<T> Split_VV( vector< vector<T> > &v , int n )
									{
									vector<T> nu( SIZE(v) );
									F_all(i,v)
										{
										nu[i]	=	v[i][n];
										}
									return	nu;
									}

								//	ranges can be EXTREMELY slow due to VI. Might want to use int[] array.
								void Range( VI &rng, int f, int t )	//	int range [F , T]. F>T is Okay
									{
									if	(f<=t)
										{
										rng.resize(t-f+1);
										F_I_F_T_UP(i,f,t)
											rng[i-f] = i;
											}
										}
									else
										{
										rng.resize(f-t+1);
										F_I_F_T_DOWN(i,f,t)
											rng[i-t] = i;
											}
										}
									}

								void Range_To_Center( VI &rng, int f, int t )	//	int range [F , T]. F<=T
									{
									rng.resize(t-f+1);
									int co;
									co = f;
									F_I_F_T_S_UP(i,f,t,2)
										rng[i-f]	=	co;
										co++;
										}
									co = t;
									F_I_F_T_S_UP(i,f+1,t,2)
										rng[i-f]	=	co;
										co--;
										}
									}

								template <class T, class U>
								vector<U> SORT_LARGE_FIRST_BY_OTHER_V( vector<U> &v, vector<T> &by_values )
									{
									vector< pair<T, int> > srt( SIZE(v) );
									F_all(i, v)
										{
										srt[i].A	=	by_values[i];
										srt[i].B	=	i;
										}
									SORT_LARGE_FIRST( srt );
									vector<U>	res( SIZE(v) );
									F_all(i, v)
										{
										res[i] = v[ srt[i].B ];
										}
									v	=	res;
									return res;
									}

								template <class T, class U>
								vector<U> SORT_SMALL_FIRST_BY_OTHER_V( vector<U> &v, vector<T> &by_values )
									{
									vector< pair<T, int> > srt( SIZE(v) );
									F_all(i, v)
										{
										srt[i].A	=	by_values[i];
										srt[i].B	=	i;
										}
									SORT_SMALL_FIRST( srt );
									vector<U>	res( SIZE(v) );
									F_all(i, v)
										{
										res[i] = v[ srt[i].B ];
										}
									v	=	res;
									return res;
									}

								template <class T>
								void SORT_LARGE_FIRST_INDICES_BY_VALUES_FROM_ARRAY( vector<int> &v, vector<T> &by_values )
									{
									vector< pair<T, int> > srt( SIZE(v) );
									F_all(i, v)
										{
										srt[i].A	=	by_values[ v[i] ];
										srt[i].B	=	v[i];
										}
									SORT_LARGE_FIRST( srt );
									v	=	Split_Pair_1(srt);
									}
								template <class T>
								void SORT_SMALL_FIRST_INDICES_BY_VALUES_FROM_ARRAY( vector<int> &v, vector<T> &by_values )
									{
									vector< pair<T, int> > srt( SIZE(v) );
									F_all(i, v)
										{
										srt[i].A	=	by_values[ v[i] ];
										srt[i].B	=	v[i];
										}
									SORT_SMALL_FIRST( srt );
									v	=	Split_Pair_1(srt);
									}


								template <class T>	
								T	V_Median(vector<T> v)
									{
									vector<T> x = v;
									SORT_SMALL_FIRST(x);
									return	x[ SIZE(x)/2 ];
									}




								template <class T>
								map<T, int> Count_Occurrences_In_V(vector<T> &v) 
									{
									map<T, int> m;
									F_elem(e,v)
										{
										m[ e ]++;
										}
									return m;
									}

								template <class T>
								int Count_Occurrences_Of(vector<T> &v, T &x)
									{
									int	s=0;
									F_E(v,e)
										if(e == x)
											s++;
										}
									return s;
									}

								template <class T>
								vector< pair<T, int> > Add_Index(vector<T> &v) 
									{
									vector< pair<T, int> >	nu;
									F_all(i,v)
										{
										nu.PUSH_XX(v[i],i);
										}
									return	nu;
									}

								template <class T, class U>
								vector< pair<T, U> > Combine(vector<T> &a,  vector<U> &b) 
									{
									vector< pair<T, U> >	nu;
									F_all(i,a)
										{
										nu.PUSH_XX(a[i],b[i]);
										}
									return	nu;
									}

								template <class T>
								void out_line_V(const vector<T> &v, ostream &c = cout) 
									{
									F_all(i,v)
										{
										c	<<	v[i]	<<	" ";
										}
									c	<<	END;
									}

								template <class T>
								void out_line_VV(const vector<T> &v, ostream &c = cout) 
									{
									F_all(i,v)
										{
										out_line_V(v[i], c);
										}
									c	<<	END;
									}

								template <class T>
								void out_line_VP(const vector<T> &v, ostream &c = cout) 
									{
									F_all(i,v)
										{
										c	<<	v[i].A << " "	<<	v[i].B	<<	" | ";
										}
									c	<<	END;
									}

								// template <class T>
								// void out_vals_at_indices(vector<T> &v, VI &ind) 
								// 	{
								// 	F_all(i,ind)
								// 		{
								// 		std::cout	<<	v[ ind[i] ]	<<	" ";
								// 		}
								// 	std::cout	<<	END;
								// 	}

								void	create_folder(string	folder_path)
									{
									string	mkdir	=	"mkdir -p " + folder_path;
									system(mkdir.c_str());
									}


								template <class T>
								int count_positive(vector<T> &v) 
									{
									int	x=0;
									F_E_WHERE(v,e, e>0)
										x++;
										}
									return x;
									}

								inline LD	dist_3(long double x, long double y, long double z)
									{
									return sqrt(x*x + y*y + z*z);
									}
								inline LD	dist_2(long double x, long double y)
									{
									return sqrt(x*x + y*y);
									}

								template <typename T,typename U>                                                   
								std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {   
									return {l.first+r.first,l.second+r.second};                                    
								}                                                                                  
								template <typename T,typename U>                                                   
								std::pair<T,U> operator-(const std::pair<T,U> & l,const std::pair<T,U> & r) {   
									return {l.first-r.first,l.second-r.second};                                    
								}                                                                                  

								template <class T, class S, class C>
									S& Container(priority_queue<T, S, C>& q) 
										{
										struct HackedQueue : private priority_queue<T, S, C> 
											{
											static S& Container(priority_queue<T, S, C>& q) 
												{
												return q.*&HackedQueue::c;
												}
											};
										return HackedQueue::Container(q);
										}

								template<typename T>
								void print_queue(T& q) 
									{
									while(!q.empty()) 
										{
										std::cout << q.top() << " ";
										q.pop();
										}
									std::cout << '\n';
									}

								template<typename T>
								string V_To_STR(vector<T> & v) 
									{
									string	x="";
									F_elem(e,v)
										{
										x	+=	STR(e) + " ";
										}
									return x;
									}

								template<typename T>
								void	out_VP(const T & a)
								{
									OUT( SIZE(a) )
									F_all(i,a)
									{
										OUT( a[i].A, a[i].B );
									}
									return;
								}

								template<typename T>
								void	out_V(const T &a)
								{
									COUT( SIZE(a) )
									F_all(i,a)
									{
										OUT( a[i] );
									}
									return;
								}
								template<typename T>
								void	out_VV(const T &a)
								{
									OUT( SIZE(a) )
									F_all(i,a)
									{
										out_V( a[i] );
									}
									return;
								}

								template<class T>
								constexpr const T& CLAMP( const T& v, const T& lo, const T& hi )
									{
									assert( !(hi < lo) );
									return (v < lo) ? lo : (hi < v) ? hi : v;
									}

								template<typename T>
								string	INT_to_str(T i)
									{
									string	x,pre;
									if	(i==0)
										return "0";
									if	( i < INT 0)
										{
										pre = "-";
										i = -i;
										}
									if	( i < INT 0)
										{
										return "INF";
										}
									while(i>0)
										{
										x	=	CHAR_STR((int)'0' + ( INT i % INT 10)) + x;
										i  /=	10;
										}
									return	pre+x;
									}

								template<class T>
								vector<vector<T>> transpose(vector<vector<T>> &vv)
									{
									if (vv.size() == 0)
										return vv;
									vector<vector<T> > trans_vec(vv[0].size(), vector<T>());
									for (int i = 0; i < vv.size(); i++)
										{
										for (int j = 0; j < vv[i].size(); j++)
											{
											trans_vec[j].push_back(vv[i][j]);
											}
										}
									return trans_vec;
									}


								inline bool	 smaller_B__pair_int_double	(const pair<int,double> &a, const pair<int,double> &b)
									{
										return	( a.B < b.B );	//	smaller
									}
								inline bool	 smaller_B__pair_int_float	(const pair<int,float> &a, const pair<int,float> &b)
									{
										return	( a.B < b.B );	//	smaller
									}
								inline bool 	smaller_B__pair_int			(const pair<int,int> &a,	const pair<int,int> &b)
									{
										return	( a.B < b.B );	//	smaller
									}


								inline bool 	larger_B__pair_int_double	(const pair<int,double> &a, const pair<int,double> &b)
									{
										return	( a.B > b.B );	//	larger 
									}
								inline bool 	larger_B__pair_int_float	(const pair<int,float> &a,	const pair<int,float> &b)
									{
										return	( a.B > b.B );	//	larger 
									}
								inline bool 	larger_B__pair_int			(const pair<int,int> &a, 	const pair<int,int> &b)
									{
										return	( a.B > b.B );	//	larger 
									}
								inline bool 	larger_B__pair_P_II_int			(const pair<P_II,int> &a, 	const pair<P_II,int> &b)
									{
										return	( a.B > b.B );	//	larger 
									}

								// public static int[] merge(int[] a, int[] b) {

								// 	int[] answer = new int[a.length + b.length];
								// 	int i = 0, j = 0, k = 0;

								// 	while (i < a.length && j < b.length)  
								// 		answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

								// 	while (i < a.length)  
								// 		answer[k++] = a[i++];

								// 	while (j < b.length)    
								// 		answer[k++] = b[j++];

								//     return answer;
								// }

								template<typename T>
								void	insert_val_in_sorted_v(T x, vector<T> &v)
									{
									if ( !SZ(v) )
										{
										v.PUSH(x);
										return;
										}										
									int larger = UP_BOUND_I(v,x);
									v.resize( SZ(v) +1 );

									F_I_F_T_DOWN(i, SZ(v)-2, larger)
										v[i+1] = v[i];
										}
									v[larger] = x;
									}


								template<typename T>
								int	Count_Intersection(const vector<T> &a, const vector<T> &b)
									{
									vector<T>	c( min( SZ(a), SZ(b) ) );
									typename vector<T>::iterator it;
									it = set_intersection(ALL(a),ALL(b),c.begin());
									return it - c.begin();
									}

								template<typename T>
								vector<T>	Intersection(const vector<T> &a, const vector<T> &b)
									{
									vector<T>	c( min(SZ(a), SZ(b)) );
									typename vector<T>::iterator it;
									it = set_intersection(ALL(a),ALL(b),c.begin());
									c.resize(it - c.begin());
									return c;
									}


								LD	SQRT2	=	sqrt(2);
								LD	SQRT3	=	sqrt(3);
								LD	SQRT5	=	sqrt(5);
								VLD	SQRT={0};
								void	pregenerate_SQRT(int x=5000)
									{
									SQRT.resize(x+1);
									F_I_F_T(i,1,x)
										SQRT[i] = sqrt(i);
										}
									}
								

								const VI		AROUND_4X	=	{0,0  ,1,-1};
								const VI		AROUND_4Y	=	{-1,1 ,0,0};
								const VP_II		AROUND_4PXY	=	{{0,-1},{0,1}  ,{1,0},{-1,0}};
								// F_E(AROUND_4PXY , aro)
								// 	int	n_x	=	CLAMP( aro.A + x	,	0	,	m_width - 1 );
								// 	int	n_y	=	CLAMP( aro.B + y	,	0	,	m_height- 1 );
								// 	}

								const VI		AROUND_8X	=	{0,0 	,1,-1	,1,-1	,-1,1};
								const VI		AROUND_8Y	=	{-1,1	,0,0	,1,-1	,1,-1};
								const VP_II		AROUND_8PXY	=	{{-1,-1},{0,-1},{1,-1},		{-1,0},		 {1,0},		{-1,1},{0,1},{1,1}};
								const VP_II		AROUND_9PXY	=	{{-1,-1},{0,-1},{1,-1},		{-1,0},{0,0},{1,0},		{-1,1},{0,1},{1,1}};











int main(int argc, char* argv[])
	{

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	srand ( unsigned ( time(0) ) );
	TIME(time_start);

	SET_COUT_PRECISION(20)
	SET_COUT_FIX_PRECISION

	#ifdef BZ
		cin.clear();
		freopen("/home/i/C/jam/libraries/ins/a", "r", stdin);
	#endif

	// LL	prm = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47;
	// DB(prm)


	// CIN_I(TST)
	// F(TST,tt)
		{
		CIN_LL(a,b,n)

		LD x = min(n+0., max(0., b-1.));
		LL q =
				floor( x * (LD_ a) / (LD_ b) )
			-	a* floor( x / (LD_ b) )
			;
// 		DB(				floor( x * (LD_ a) / (LD_ b) )
// 			,x * (LD_ a) / (LD_ b)
// )

		COUT(q);

		// F(1000,i)
		// 	if(a*i<=t && a*i>=f)
		// 		{
		// 		a = -1;
		// 		break;
		// 		}
		// 	}
		
		// if(a==-1)
		// 	COUT("OK")
		// else
		// 	COUT("NG")

		// CaseOUT( tt+1	,	re	 )
		// Case #1: TPFOXLUSHB
		// CaseOUT_empty( tt+1 )
		}


	// CERRY(TIME_SINCE(time_start))
	return 0;
	}

Measured memory_bytes: 3692