/*DEP TRAI CO J SAI*/
/* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%##***************************+++++++++++++++++++++++++++++++++++++++++++++++***************************######%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%####**************************++++++++++++++++++++++++++++++++++++++++++++++++***************************#######%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@%%##**************************++++++++++++++++++++++++++++++++++++++++++++++++++****************************########%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%##***************************+++++++++++++++++++++++++++++++++++++++++++++++++++++++************************#########%%@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%##*************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************##########%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%##*************************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++**+*********************#############%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%##*************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*********************########*######%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%####********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************######**#######%%%@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%%##**************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++************************#####***#######%%@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%##***********************+*****+++++++++++++++++++++++++++++++++++++++++++++++++++++++++***********************######***######%%%@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%##******************************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************####****#####%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@%%%####*****************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++***********************###****########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@%%%####***************************++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++**********************#****#########%%@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@%%###*****************************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************########%%%@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%%###******** ************************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*********************###**########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%#####****************############*********++++++++++++++++++++++++++++++++++++++++++++++++++************###***#####################%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%#####************##%%%%%%%%%%%%%%%%%%%%%##***+++++++++++++++++++++++++++++++++++++++++++***####%%%%%%%@%%%%%%%%%%%%%################%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%######*******##%%%@@@@@@@@@@%%%%%%%%%@%%%%%%%##****++++++++++++++++++++++++++++++++++**###%%%%%%%%%%@@@@@@@@@@@@@@@@@%%##***#########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%######*****#%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%####***++++++++++++++++++++++++++***###%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@%%%###########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%#####****##%%%###%%%###**######%%%%%%%%%%%%%%%%%%%%%###***+++++++++++++++++++++******##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@%%#########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%#####***#######**********+**********####################***+++++++++++++++++++******#######%%%%%%%%%#######*******####%%%%@%#########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%####*****************+++++++++++++++++************#*###****+++++++++++++++++++*****#######************+++++************##%%%%########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%###***#*******++**+++++++++++++++++++++++*****************+++++++++++++++++++*****##**************+++++++++++++++*******###%%#######%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%###****************+++++++++++++++++++++++++*************++++++++++++++++++++*****#**********+++++++++++++++++++++********#########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%##*****************++*+++*******************************+++++++++++++++++++*******##******+++++++++++++++++++++************########%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%##*******************************######**#####**********+++++++++++++++++*****#####*******+++++++++*+***++++****************###**##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%##***************##**####%%%%@@%%%%%%%%%%%##************++++++++++++++++******##************++++++++*****************************##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@%%##%%@@@%%#***************#####%%@@%##%%##*#%%####**##%##*************+++++++++*******#####*********######%%%%%%#############*#**********####%###%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@###***##%@%##************###%%@@@@@%%#**####%%%%##***++**#####*+***********+++++********###****#######****#***#%%%%%%%%%%%%######***********#########%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@###******#%##**************##%%%%########********************+++**********++++++*******###*****####****++**###%%%######%%@@%%%%#####**********###***#%%%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@%#*##******##***********+++*******************++********++++++++**********++++++********####*******************##########%%%@@@@%%####*********##%####%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@%#*##******###******++++++++**********++**+*************++++++************++++++********####**********++**+++********#######%%%%%%###**********########%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@#**##*****###*******+++++++++++++++++****************++++++++*************++++**********######*****************************#######**************##**####%@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@%*********####********++++++++++++++++++++++++++++++++++++++++**************++**+*********####********++++******************************************#####%@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@%********#####********+++++++++++++++++++++++++++++++++++++++++*************++++++*********####*******++++++++++++++++++++***********************#########%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@%*******######*******++++++++++++++++++++++++++++++++++++++++************+++++++++++********###*******++++++++++++++++++++++++++++*************#####*#####%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##########%%%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@#**+++**#%###********+++++++++++++++++++++++++++++++++++++++***********++++++++++++++++*******#*******+++++++++++++++++++++++++++++++**********#####**####%%@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###%######%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@@#*++++**#####*******+++++++++++++++++++++++++++++++++++++++**********++++++++++++++++++++******##*****++++++++++++++++++++++++++++++++*********##*###**###%%@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###%#################%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@%#*++***######*******++++++++++++++++++++++++++++++++++++++********++++++++++++++++++++++++***********+++++++++++++++++++++++++++++++++++*******##*###****#%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#####################%%%%%%%%*
@@@@@@@@@@@@@@@@@@@@%*++****#####********+++++++++++++++++==+++++++++++++++++++****++++++++++++++++++++++++++++************++++++++++++++++++++++++++++++++++*******#**###****#%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%#################################%%%%%%*
@@@@@@@@@@@@@@@@@@@@%**+****#%%###*******++++++++++++++++++++++++++++++++++++++**+++++++++++++++++++++++++++++**************+++++++++++++++++++++++++++++++++**********##*****#%@@@@@@@@@@%%%%%%%%%%%%########################################%%%%%%*
@@@@@@@@@@@@@@@@@@@@%#*****##%%###*******+++++++++++++++++++++++++++++++++++++***++++++*********++++++++++++****************+++++++++++++++++++++++++++++++++***********#*****#%@@@@@@@@@@%%%%%%%%############################################%%%%%%*
@@@@@@@@@@@@@@@@@@@@%#*****##%%###*******+++++++++++++++++++++++++++++++++++++**++***#%%@@@@@@@%#*++++++++**##%@@%%##********++++++++++++++++++++++++++++++++***********##****#%@@@@@@@@@@%%%%%%%#############################################%%%%%%*
@@@@@@@@@@@@@@@@@@@@@#******#%%####*******++++++++++++++++++++++++++++++++++++******###%%@@@@@%##***++++***#@@@@@@%%###*******+++++++++++++++++++++++++++++++******#****###**#%%@@@@@@@@@@%%%%%%%#############################################%%%%%%*
@@@@@@@@@@@@@@@@@@@@@%******#%%####*******++++++++++++++++++++++++++++++++++++*************#**************##%%%%%%##**********+++++++++++++++++++++++++++++************####**#%@@@@@@@@@@@%%%%%%%#############################################%%%%%%*
@@@@@@@@@@@@@@@@@@@@@@#*****#%%%###*********++++++++++++++++++++++++++++++++++******+++++++++++*********###********+++***#*****+++++++++++++++++++++++++++*************#%#####%@@@@@@@@@@@%%%%%%%##############################################%%%%%*
@@@@@@@@@@@@@@@@@@@@@@%#****#%%%%##**********++++++++++++++++++++++++++++++++++********+++++++*************************####****++++++++++++++++++++++++****************#%#**#%%@@@@@@@@@@@%%%%%%###############################################%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@%%%%##%%%%###*********+++++++++++++++++++++++++++++++++++++******+++++++++++***************#######*******++++++++++++++++++++++*****************%%###%%@@@@@@@@@@@@%%%%%%%##############################################%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%####************++++++++++++++++++++++++++++++++++++++++*++++++++++++++++*********************++++++++++++++++**********************#%%%%%%@@@@@@@@@@@@%%%%%%%%##############################################%%%%%*
@@@@@@@@@@@@@@@@@@@@@@@%##*#%%%%%%######***********++++++++++++++++++++++++++++++++++*+****#*****+++++++***#####********************++++++++++++******************##*#%%%%%%%%@@@@@@@@@@@%%%%%%%%###############################################%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@%%###%@%%%%######*************+++++++++++++++++++++++++++*****####%%%%%%##**+**###%%%%%%%##*********************+++++*******************######%%%####%@@@@@@@@@@@%%%%%%%################################################%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%#######**********+++++++++++++++++++++++++****###%#%%%%%%%%%%#****##%%%%%%%%%%%%##****************************************########%%%###%%%@@@@@@@@@@%%%%%%%#################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%######*********++++++++++++++++**********####%#%%%%%%%%%%%%%####%%###%%%%%@@@@%%###**********************************##########%%%####%%%%%@@@@@@@%%%%%%%%#################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%#######************++****+******########%%%%###***********#######*****####%%%%%%%%%######**************************######%%%%##%#####%%%%%@@@@@@%%%%%%%%%################################################%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%#####**********************####%%%%%#####**********++++++******************###%%%%%%%#####*******************########%%%%%%#%%######%%%%%%%%%%%%%%%%%%#################################################%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%#%#####******************######%%###*******************************************##%#%%%%%%####***************#########%%%%%%%%#######%%%%%%%%%%%%%%%%%%##################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%#%%%%%%%#####***************##########****************************************######*#####%%%%%%%#######*******########%%%%%%##%#%########%%%%%%%%%%%%%%%%%##################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%###%%%%%#####**************#########********################################################%%%%%%%#####*****######%%%%%%%%%##%%%%########%%%%%%%%%%%%%%%%%#################################################%%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%##%%%%%%######************#####****#########################################################%%%%%%%##############%%%%%%%%%#%%%%%#########%%%%%%%%%%%%%%%%###################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%#####***********####***###############*####****####**###############################%%%%%############%%%%%%%%%%%%%%%%##########%%%%%%%%%%%%%%%%####################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%###**********##***#####%%#####**********************************#####%%%%%#########%%%###########%%%%%%%%##%%%%%%%##########%%%%%%%%%%%%%%%%###################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%###**************########*************+++++++++++++++*************#############*###############%%%%%%%%##%%%%%%%%##########%%%%%%%%%%%%%%%####################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%###****************######********++++++++++++++++++++++++++*******###########******#########%%%%%%%%%%%#%%%%%%%%############%%%%%%%%%%%%%%####################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%####***************************+++++++++++++++++++++++++++++*********#######******##########%%%%%%%%%%%%%%%%%%%##############%%%%%%%%%%%%%####################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%%%%%%%%###******************************++++++++++++++++++++++++++*********########****###########%%%%%%%%%%%%%%%%%%%##############%%%%%%###########################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@@@@%%%###*****************##*****************+*****************************#######***###########%%%%%%%@%%%%%%%%%%################%%%%%############################################################%%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@@%%@@@@@@%%%#####**************######***************************************#########*****###########%%%%%@@@@%%%%%%%%######****#######%%%%%%%###########################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%@@@@@@@@%%%######******************###########%#%%%%%%%%%%%%%%%%%%%%%%%##########*******###########%%%@@@@@@@@@%%%%%#####***#**#######%%%%%%############################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%@@@@@@@@@%%%#####*********************######%#####%%%%%%%%%%%%%%%%#%%%%####***********#############%%%@@@@@@@@@@@%%####*******#########%%%%%############################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%####%%@@@@@@@@%%%######*************************############%%%%%%%%%%#####***************############%%%%@@@@@@@@@@%%###*#*******#########%%%%%############################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#####%%%%@@@@@@@%%#####**********************++++************####*#######***************#############%%%%@@@@@@@@@%%%%#***********#########%%%%%############################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%#######%@@@@@@@%%%%####****************+++++++++++++++++++++*+++*+*******************##############%%%%@@@@@@@@%%%%%##************#######%%%%%%############################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#######%%%%@@@@%%%%%###***************+++++++++++++++++++++++++++++++++++************##############%%%%@@@@@@@%%%%###*************#######%%%%%%############################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##****###%%%@@@@@%%%%%##*************+++++++++++++++++++++++++++++++++++++****************#######%%%%@@@@@@@@%%######*************#######%%%%%%%%##########################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##******###%%%@@@@@@%%%##************+++++++++++++++++++++++++++++++++++++***************######%%%%%@@@@@@@%%%#######*************#######%%%%%%%%%%########################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##*********##%%%%@@@%%%%##******++++++++++++***+++++*++++++++++++**++********************####%%%%@@@@@@@@@%%%#######**************#######%%%%%%%%%%#########################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##***********###%%%@@@@%%%##****++++********************++++++++************************##%%%%%%@@@@@@%%%%#####*#####**************######%%%%%%%%%%%########################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%###************###%%@@@@%%%##******+*******#****###******************##########*****#####%%%%%%@@@@@%%%%####*#***###**************#######%%%%%%%%%%%%######################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##**************##%%%@@@@%%####******##############****#****#########%%%%%%%#######%%%%%%%%@@@@%%%%######********##**************#######%%%%%%%%%%%%%#####################################################%%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##****************##%%%@@@@%%######*#########################%%#%%%%%%%%%%%%%%%%%%%%%%%%@@@@@%%%%%####***********##**************######%%%%%%%%%%%%%#######################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##*****************###%%%%@@@%%%%%%%%%%%%%%%%%%%%%%%%%#%####%%%%%%%%%%%%%@@%%%%%%%%@@@@@@@@%%%%%####*************##**************#######%%%%%%%%%%%%#######################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##*************++*****##%%%@@@@@@@%%@%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@%%%%@@@@@@@@%%%%%####***************##****************#####%%%%%%%%%%%%#######################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##**********+++++*******###%%@@@@@@@@@@@@@@@@@@@@@@@@@%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%####***************#*#*****************#####%%%%%%%%%%%%%######################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%##********+++++++++++******#%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%####********************##****************#####%%%%%%%%%%%%%######################################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%%%#******++++++++++++++++++******####%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###*********************************************#####%%%%%###############****#########################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%*++============================================================================================================================================================================++*#################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#+==================================================================================================================================================================================+################################%*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#+===================================================================================================================================================================================+*################################*
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#+====================================================================================================================================================================================*################################*
@@@@@@@@@@@@@@@@@@@@@@@@@%%%#*==============================================*%@@@%*=============================================================+#%%#+========+*##*+==+##*=========================================*################################*
@@@@@@@@@@@@@@@@@@@@@%%%#####+==========+%@@@@@@@@@@@@@@@%#*+==============*@@@@#+===+****+====================================================*%@@@@%*======*%@@@@@%#%@@#+==+****+================================*################################*
@@@@@@@@@@@@@@@@%%%#####*****+==========+%@@@@@@@@@@@@@@@@@@@#+===========*@@@%*=====#@@@@*===+*%@@@@#+========================================+#@@@@#+=====+#@@#*#%@@@@%+==+#@@@%*================================+################################*
@@@@@@@@@@@%%%#####**********+==========+%@@@@@#*++++**#@@@@@@%+=========+****+====+#@@@@#+====#@@@@@#+==========================================++++=======+***+==++***==+*#@@@@#+================================+################################*
@@@@@%%%%#####***************+==========+%@@@@@*========*@@@@@@+========++**##%%%%@@@@@@#+==+**%@@@@@%****===============++*####*++==+*****+===+******+========+**###%%%%@@@@@@%*+=+******==+**####*++=============+################################*
%%%######********************+==========+%@@@@@*========*@@@@@%+======*#@@@@@@@@@@@@@%*=====#@@@@@@@@@@@@%+============+#@@@@@@@@@@#*%@@@@@*===+@@@@@%+=====+#%@@@@@@@@@@@@@#++====*@@@@@%*%@@@@@@@@@%*+===========*###############################%*
#####*****************+++++**+==========+%@@@@@#++++++*#@@@@@#+=====+#@@@@@@@%%%@@@@@@%*+===*%%@@@@@@@%%%#+===========*@@@@@@@@@%@@@@@@@@@@*===+@@@@@%+===+#@@@@@@@%%%@@@@@@@#+====*@@@@@@@@@@@@@@@@@@@#+==========*###############################%*
**************++++++++++++***+==========+%@@@@@@@@@@@@@@@@%*+======+%@@@@@#+====+*%@@@@@*+====+#@@@@@%+==============*%@@@@@#*====+*%@@@@@@*===+@@@@@%+===#@@@@@%*+====+%@@@@@%+===*@@@@@@%+====+#@@@@@%*==========*################################*
************+++++++++++++++**+==========+%@@@@@@@@@@@@@@@@@@@#*====*@@@@@%+=======*@@@@@%+=====#@@@@@%+=============+#@@@@@#+=======*@@@@@@*===+%@@@@%+==*@@@@@%*=======+%@@@@@*===*@@@@@%+======+%@@@@@*==========*###############################%*
******++++++++++++++++++++++++==========+%@@@@@*+======+*%@@@@@%+=+#@@@@@#========+%@@@@@*=====#@@@@@%+=============+%@@@@@*========+%@@@@@*===+%@@@@%+==*@@@@@%+========#@@@@@#===*@@@@@%+======+%@@@@@*==========+##############################%%*
***+++++++++++++++++++++++++++==========+%@@@@@*=========+%@@@@@#=+#@@@@@#+=======+%@@@@@*=====#@@@@@%+=============+#@@@@@#========+%@@@@@*===+%@@@@%+==*@@@@@%+=======+%@@@@@*===*@@@@@%+======+%@@@@@*==========+*******#######################%%*
+***++++++++++++++++++++++++++==========+%@@@@@*=========*%@@@@@#==*@@@@@%*======+#@@@@@%+=====#@@@@@#+==============*@@@@@@*======+#@@@@@@*===+%@@@@%+==+%@@@@@*=======*@@@@@@*===*@@@@@%+======+%@@@@@*==========+***********#####################*
+++++++++++++++++++++++++++*++==========+%@@@@@#+++++++*#@@@@@@%*===#@@@@@@#++++*%@@@@@%*======*@@@@@%*+=============+#@@@@@@%#***#@@@@@@@@*===+%@@@@%+===*%@@@@@#*+++*#@@@@@@*====*@@@@@%+======+%@@@@@*==========+***************#################*
**+*+++++++++++++++++++++++**+==========+%@@@@@@@@@@@@@@@@@@@@#+=====*%@@@@@@@@@@@@@@@#+=======+%@@@@@@@@%+===========+*%@@@@@@@@@@%#%@@@@@*===+%@@@@%+====*%@@@@@@@@@@@@@@@%*=====*@@@@@%+======+%@@@@@*==========+**********######################*
*****++++++++++++++++++++++**+==========+%@@@@@@@@@@@@@@@@%#*+=========+#%@@@@@@@@%%*+==========+#%@@@@@@%+==============+*#%%%%#*+++%@@@@@*===+%@@@@%+======+#%@@@@@@@@@%#++======*@@@@@#+======+%@@@@%*==========+*###############################*
##*************++++++++******+=============================================+++++++==================++++++===========+******+=======*@@@@@%+=====================+++++++===========================================*#######*******##################*
#########********************+=======================================================================================+#@@@@@@%#**##%@@@@@%*========================================================================+##**************################*
#################************+=========================================================================================+#@@@@@@@@@@@@@@%*+=========================================================================+*****************###############*
*****########################*============================================================================================+**#######*++============================================================================+*****************##*############+
*********####################*=====================================================================================================================================================================================+********************************+
***************###############+===================================================================================================================================================================================+*********************************+
*********************##########++================================================================================================================================================================================+**********************************+
***#*************************###***++++++++++++++++++++++++++++++++==+++++++=++++++====+++====+==========++++++=+++++++++++++++++++++=+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*************************************+ */
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define fi first
#define se second
#define pu emplace_back
#define ll long long
typedef pair <ll,ll> ii;
const int N=1e6;
long long mod=1e9+7;
ll n,m,x,y;
ll a[2][N+1],b[N+1],L[N+10],R[N+11],ans,c[N+10];
void calc(){
for(int i=1;i<=n;i++){
c[i]=a[b[i]][i];
}
stack <int> s;
for(int i=1;i<=n;i++){
while(s.size()){
if(c[s.top()]<=c[i]) s.pop();
else break;
}
if(!s.size()) s.push(i);
L[i]=s.top();
}
while(s.size()) s.pop();
for(int i=n;i;i--){
while(s.size()){
if(c[s.top()]<=c[i]) s.pop();
else break;
}
if(!s.size()) s.push(i);
R[i]=s.top();
}
for(int i=1;i<=n;i++){
ll d=min(c[L[i]],c[R[i]]);
ans+=d-c[i];
}
}
void bt(int t){
for(int i=0;i<=1;i++){
b[t]=i;
if(t==n) calc();
else bt(t+1);
}
}
void sub1(){
bt(1);
cout<<ans%mod;
}
void tinh(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[0][i];
for(int i=1;i<=n;i++) cin>>a[1][i];
if(n<=20){
sub1();
return;
}
}
int main(){
ios_base::sync_with_stdio(false);
//freopen("jday.inp","r",stdin);
//freopen("jday.out","w",stdout);
cin.tie(0);
cout.tie(0);
tinh();
return 0;
}
//code của anh Nam đẹp trai nhất CHL
