/*
IIIIIIIIIIII??IIII?????????????????????????????????????????7$$$$$$$$$$$$$$ZZZZZZZZZZZZZZZZZ$$$$$$$$7$???????????????????????????????????????????????????????????????????????????????????????????IIIIII 
IIIIIIIIIIII??IIII??????????????????????????????????????7$$$$$$$$$$$$$$$$ZZZZZZZZZZZZZZZZZ$$$$$$$$$$$7$???????????????????????????????????????????????????????????????????????????????????????????IIIIII
IIIIIIIIIIIIIIIIII??????I?????????????????????????????7$$Z$$$$$$$$Z$$$ZZZZZZZZZZZZZZZZZZZZ$$$$$$$$$$$$$$$7+???????????????????????????????????????????????????????????????????????????????????IIIIIIIIII
IIIIIIIIIIIIIIIIIIII?????????????????????????????????$$ZZ$$$$$$$ZZ$$$ZZZZZZZZZZZZZZZZZZ$$$$$$$$$ZZ$$$$$$$$$I??????????????????????????????????????????????????????????????????????????????IIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIII??????????????????????????????I7$ZZZ$$$$$ZZZZZ$ZZ$ZZZ$$ZZZZZZZZZZZ$$$$$$ZZZZZZ$$$Z$$$$$$$I????????????????????????????????????????????????????????????????????????IIIIIIIIIIIIIIIIII
????IIIIIIIIIIIIIIII??????????????????????????????ZZZOZZZZZZZZZ$ZZZ$$ZZ$$ZZZZZZZZZZZ$$$$$$ZZZZZZZ$$Z$ZZ$$$$$$$$???????????????????????????????????????????????????????????????????????IIIIIIIIIIIIIIIIII
=~=?IIIIIIIIIIIIII?????????III??????????????I???7ZZOOZZZZZZZZZZZZZ$ZZZ$$ZZZZZZZZZZ$77$$77$$$$Z$$77$77$ZZ$Z$$$$$$I???????????????????????????????????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIII
+??I?IIIIIIIIIII??+===~=????II????????????????I$ZZOOOZZZZZZOZZZZZZZZ$$$$$$$$$$$Z$$$$$$$$$$$$Z$$$77$$77777ZZ$ZZZ$$I??????????????????????????????????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIII???+=~~~~+???????????????????I$ZOOOOZZZZZOOZZZZZ$$$$$$$$$$$$$$Z$$$$$$$$$$$7ZZ$$$$7$$$77$$Z$$$ZZZ$ZI???????????????????????????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIII?????+????????II????????IZZOOOOOZZZOOO$Z$$$$$$$$$$$$$$$$Z$$$$$$$$$$$$$$Z$$$$$~$$?I7$$$$$Z$ZZZZ$$I?????????????????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIII?II??????I???IIII????II??7ZOOOOOOZZZ$$$$$$$$$$$$$$$$$$$$Z$$$$$$$$$$$$ZZZZZZZZ=~Z$~~ZZZ$Z$$Z$$$ZZ$$I????????????????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII????IIIIZOOOOOZ$$$$$$$$$$$$$$$$$$$$$$$ZZZ$$$ZZOZOOZZZZZZ$ZZ:~~Z$~=ZZZZOZ$O$$$$ZZ$I??????????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZOOOZ$Z$$$$$Z$$$$$$$$$$$$$$$$$ZZOZZZZOOOOOOOOOZ?7ZZ::=~Z+:~+ZZZ7OOOZ$$$O$ZZ??????????????????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??I
I?IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII$OO$$$Z$$$$$Z$$$$$$$$$$$$ZZOOOOOOZZZOOOOOOOOOO$=?Z$::~~=Z,::~OZZ=OOOOO$$$Z$$Z?===++?????????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??????
??????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII$$$$$$Z$$$$$$$$$$$$$ZZOOOOOOOOOOZZOOOOOOOOOOZ~~=Z7:::~~77:::~$ZZ+OOOOOOO$O$$$I??+???I?????????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??+:
~::=?IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII$$$$$ZZ$$ZZ$ZZZ$$$ZZZZOOOOOOOOOOOZOOOOOOOOOO7===Z=::::=:$::::~=ZZ=?OOOOOOOO$$$$II???I????????IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??=:
::::=?I?IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII?$Z$ZZZZZ$$$ZZ$ZZZOOOZOOOOOOOOOOOZOOOOO+OOZZ~=~=Z::::::~:I:::::=OZ==OO$OOOOOZ$$$II??IIII??IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??~:
::::~+IIII?IIIIIIIIIIIIIIIIIIIIIIIIIIIII$ZZZZZZZZZZZZZOOOOOOOOOOOOOOOOOOOOOOO~IOOZ~=::=:::::::::?::::::=$Z:=ZO=OOOOOOZ$$$IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII???=~::
::::~=???????IIIIIIIIIIIIIIIIIIIIIIIIIII$ZZZZZ$ZZZZZZZOOOOO8OOOO88OOOOOOOO8+=7ZZ==~::::::::::::::::::::~?Z:=IO=OOOOOOOZ$$?IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??=~~::,::
~~~~~=+?+++++???IIIIIIIIIIIIIIIIIIIIIIII$ZZZZZZOO88OOOOOOO8OO888888OOOOOO?==8O+~=:::::::::::::::::::::::~$:=+Z=$OOOOOOZZ$7IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII?IIIIIII??+~::::,:::
~~~:~~=???+++??IIIIIIIIIIIIIIIIIIIIIIII$ZZZO8888888OOOOOO888O888888888OI===O=~=O+::::::::::::::::::::::::::~=O==OOOOOOZZZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII???IIIIIII?=:,::,,::::
~~~~~~~=+?IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZO88888888OOOOOOO888888888888OZZZOZZ7=:=~ZZ:::::::::::::::::::::::::~O==OOOOOOOOOZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII???I?IIII?+~:,,::::~~
~~~~~~~~=+++??IIIIIIIIIIIIIIIIIIIIIIIIIZ8888888888OOOOOO88888888888OZ+?7OOOO8OZZZZ7OZ,:~:::::::::::::::::::::7==OOOOOOOOOZIIIIIIIIIIIIIIIIIIIIIIIIIIII????IIIIIIIIIIIIIIIIIIIIIIIII?==+++????=:,::::::~~
~~~~~~~~~~~==??IIIIIIIIIIIIIIIIIIIIIIIIO8888888888OOOOOO8888888888OZ+=ZOOO+=8OO8OOOZ$$$:::::::::::::::::::::::~=$8OOOOOOOO7IIIIIIIIIIIIIIIIIIIIII?????=~:~=+?IIIIIIIIIIIIIIIIIII??=~:::::~~~~:,,::::::::
~~~~~~~~==+?IIII??IIIIIIIIIIIIIIIIIIII78888888888OOOOOOO888888888OZZO88+===OZ$ZZZO8O$OZ$+:::::::::::::::::::::~=IOO888OOOO$IIIIIIIIIIIIIIIIIIIII?+~~::,,,::~+IIII???IIIIIIIIIIIII+:,,:::::::::::::::::~~
+===+???????IIIIII??????IIIIIIIIIIIIII$8888888888OO8OOO8888888888OZZ:8+=~,,O77$O7$O=$O+7ZZ$::::::::::::::::::::++O8888OOOOZIIIIIIIIIIIIIIIIIII??+~,,::::::~~+??+=====+IIIIIIII?+=:,:::::::::::::::::~~~~
III?IIIIIIIIIIIIIIII????IIIIIIIIIIIIIIO8888888888OOOOOO8888888887+OO=:Z~,,,Z,$Z8I7O~~~I==ZZOOOZ$:~::::=?$OO?~::=+O8888OOOOZIIIIIIIIIIIIIIIIII?=~::::::::~~~~~~~~=====?IIII?+++=~::::::::::::~~::::~~::::
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8888888888OOOOOO8888888888==OZ$::::,::,,7I~:7,:::::OOOOOZZZZ7OZZZZZOZZZZ$Z+O8888OOOOZIIIIIIIIIIIIIIIIII?=~:::::::~~~~~~~~=+???IIIIII?~::::::::::~~~~~~~~~:~~~:::~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8888888888OOOOOO888888888O=:~OZ::::,:,O?=++O,:::::=ZZOOOZZZZIZ?8888O87:IOZ$88888O8OOOIIIIIIIIIIIIIIIIII??+===~~=++++??++??IIIIIIIIII?+~~~==~~~:~~~~~~~~~~~~~~:::~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8888888888OO8OOO888888888I=::OZ7:~:~~,,,??,,::::::OZ+::::~=O$ZI=O$ZZOIOO:~Z88888O8OOOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??????+==~~~~=======~~::::~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8888888888OO8OO8888888O88~::::OZ+::::::~~~~~:::::OZZ:::::::~O=::7OO7O~O~:~88O88888OOOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII????I???III??====+??+==~~::::::~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII78888888888OO8OO8888888788=:::::OZZ+::~::::::::~?OOZ::::::::IZ~,?:$7+?,~::888O88888OOOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII?=::~~=~==++==~~==+++==~~:::::::~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZO888888888O88OO8888888?8O~:::::::ZOOZZZ7~:::::~8O$?::::::::=Z+,?+?:+::~:Z88O888888OOOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII?=,:,::::,:::::::~::~~:::::::::::~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIO8888888888888OO888888I+8O::::::::::~::IOOOOZOOOOO::~::::::~=OZ=:I$:,:::=8888888888OOZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII+~:,:::,:::,,::::::::::::::::::::::~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII7O8888888888888OO888888+=8Z::::::::::::::::::::::::::::::::::=IZ7:,~+::::88O8888888OOO$IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII???????+~:,,,,,,,,,,,,::,,::,,,,::::::::::::
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOO88888888D8888OO888888==OZ::::::::::::::::::::::::::::::::::II~OOZ+:~:::OO88888888OOO7IIIIIIIIIIIIIIIIIIIIIIII?+?IIII?=~~::::~~::::,,::,,,,,,,,::::,,:,::::::::::::
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOO88888888888888O888888==OZ:::::::::::::::::::::::::::::::::+7::::=8OOOOO8888888888OOOIIIIIIIIIIIIIIIIIIIII??+=::~+?++~::::::::,::::,,,,::::::,::,,:::::::::::~~~~~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII?++7OO88D888888D88D88O888888==~8::::::::::::::::::::::::::::::::~~::~::::::+O88888888888OOOIIIIIIIIIIIIIIIIII??+=~::,:::::::,,:,,::,,:,,,:::::::::,,,::::::~~~~~~~~~~~~~~
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIII??I8O88888888888888888888887==~Z::::::::::::::::::::::::::::::::::::::::::O$O8888888888OOO7IIIIIIIIIIIIIIIII?+:::::::::::::::::::::::::::~~~::::::::::::~~~~~~~~~~~~~~~~=
??IIIIIIIIIIIIIIIIIIIIIIIIIIIIII?8OO888888888888DD88888888?==~~:::::::::::::::::::::::::::::::::::::::::~IO88888888888O8OIIIIIIIIIIIIIIII???~::,:::::::::::::,:::::::~~~~~~~~~::::::::~~~~~~~~~~~~~~~::~
????IIIIIIIIIIIIIIIIIIIIIIIIII?IZ8O8888888888888DDD8888888=7==::::::::::::::::::::::::::::::::::::::::::OO88888888888O8OOIIIIIIIIIIIII???+++~::,,,,,:::::::::,,,,,:::~~~~~~~~~:::::~~~~~~~~~~~~~~~~~~:::
???I?????????IIIII????IIIIII??I7OO888888DDDDDDDDDDD8888888I?==:~:::::::::::::::::::::::::::::::::::::~7OO8D888888888888OIIIIIIIIII????+=~::::,,,,,:,,,,,:::::::::::::~~~~~~~~~:::~~~~~~~~~~~~~~~~~~~~:::
~+????????????????????????II???OOO$88D88DDDDDDDDDDD8888888==I=~:::::::::::::::::::::::::::::::::::::=ZO8$=O888888888OOO$III???????+=~~~:::::::::::::::,,::::~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=~~==~
:~=+??????????????????????????8OOO$88DDDDDDDDDDDDDDD888888===I=~:::::::::::::::::::::~:::::::::::::~~:::=+8D88888888OOOI?I$7????+==~~:::::::::::::::::::::::~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=++??????+
::::=?++?????????????????????$OO8$888DDDDDDDDDDDDDDD888888======:::::::::::::::::=??II?I$?,~~::::::::::~+8888888888OIO7I~::::~7?++=~~~~:::::~~::::::::~~~~~~~~~~~~~~~~~~~~~~===~~~~~~~~~~~==+???IIIIIIII
:::::~:~~:::=+??????????????IOO8OI888DDDDDDDDDDDDDDD888888?======:::::::::::::::::~++++??IIZ::::::::::~=88888888D8OIOO:::::::::::::$?+======++++==~~~~~~~~~~~~~~~~~~~~~:~~~=+??++=======~=+??IIIIIIIIIII
~~~::::::::~+++?+???????????8OO8Z?O88DDDDDDDDDDDDDDD888888I=======:::::::::::::::::~::::,~=:::::::::::?8888888888OI$:~::::~::::::::::7+???++???????++++===~~~~~~~~=+++==++????I???????+++=+????IIIIIIIII
~~~~~~~~~~=+++++++??++?+????OOOO?7OODDDDDDDDDDDDDDDD888888Z=======?~:::::::::::::::::::::::::::::::::88888888888O?~:::::::I~:::::::::::::$??????????????++===+==++????????????????II?????????????I??II??
++++++++++++++++++++???++++78888?O88DDDDDDDDDDDDDDDDDD8888O=========I::~::::::::::::::::~I~~?=:~::~IO8888888888O$::::::::+::::::?::::::::::$?????????????????????I???????I???????IIIIIIIIIIII???????????
??????????+++++++++++++++++ZO88$+O88DDDDDDDDDDDDDDDDDD88888===========~?:~:::::::::~:7IO~~::::::,::::::~~+IZO8$:~~::::::~::::::=+:::::::::::::ZI????????????????????????????????????????????????????????
+++++++++++++?+++++++++++++OO88I+O88DDDDDDDDDDDDDDDDDDDD8D8+=============?:::~::::II~::~:::$~~::::~~:::::::::::~:::::::==::::::=,:::::::::::::~~????????????????????????????????????????????????????????
++++++++++++++++++++++++?+?$8O87+O88DDDDDDDDDDDDDDDDDDDD8D8=================?::~~:::::::::::I:::::=::::::::::7:=+~:::~=7:::::::I:::::=+::::::::::???????????????????????????????????????????????????????
+++++++++++++++++++++++++++I888$?O88DDDDDDDDDDDDDDDDDDDD88D$================+$:~:::::7::::~:~7::~::I~~::::::~7=====7==?::::::::::::::=~::::::::::~?????????????????????????????????????????????+++++?+++
++++++++++++++++++++++++++++OO8O+ZO88DDDDDDDDDDDDDDDDD88DD8===============7::7~~::::::?:::::::::::~~=888888O??I======+::::::::I::::::=:::::::::::::???????????????????????????????????????++++++++++++++
++++++++++++++++++++++++++++78O8++888DDDDDDDDDDDDDDDDD88D88?===========+$:::::::::::~::I~:::::::?::~==88888O+++7=====7==+7?::~:::::::7::::::::=::::~????????????????++???????????????????+++++++++++++++
+++++++++++++++++++++++++++++OO8O+888DDDDDDDDDDDDDDDDD8DD8OZOZOO?+====7:::::::::::::::~:$::::::::7::==~8888O++?+7====+=======7:::::::+:~:::::I=::::::++?++????+???+++++?????????+++??????+++++++++======
++++++++++++++++++++=====+++++8O8II888DDDDDDDDDDDDDD8888+++7OZZZOZZOO::~:::::::~=~:::::::+::::::::$~==+888OO++++++7===+======~::::::~:::::::~===~:::,:I++++++++++++++++++++++++++++++++++++=============
++==========++================+OO8?8ODDDDDDDDDDDDD8888O++++++++=IOO:~~::::::~======::::::::+::::======OOOOOO=++++=====I=====+?+==+==7::::::~+=~::::::::$+++++++======+++++++++++++==================+++=
================================OOD=O8DDDDDDDDDDDD88DD+++++++++++?:~:::::::~======?==:::::::~~====I=+I====++~7+==?====7======?======$=~::~I?+=::::::::::=====~~::::~~===++++++++============++++++++++++
==========================~~~~~~~O88+8DDDDDDDDDDD888D88=+++++++7::::::::::::~~=?+==II===~===7====++++====++==++++=+==+===??$$$I=====+======7$=::::::::::::=~::::::::~~~~==============++====+++++++++++=
=====================~=~~~~~~~~~~~O88O88DDDD888O,:O88888I++++?~:~:::::::::::~====I?=I~===++?===?~=+~==+++++==I+===+7=+==I=====+?======+=====+=:::::::::::::+,::::::~~~~~================================
=================~~~~~~~~~~~~~~~~~=?8D888ZI??+78+:8888888$++7~::::::::::::::~==+=$==+=====?===?=~7+=+++++?I~==========+I+=======+II?$~=I$$??~=::::::::::::::$+~~~~~=====================================
==============~=~+7$7I?+???????????????????????8O,O8888888Z::::::::::::::::~====I========+==7++===+++?IO+================I==================I+=:::::::::::::7$I===========~~============================
==========~~~=I++?????????????????????????????I8O,I88888O$:~::::::::::::::~=====?=======I?+====+++++$OO====================I=================+=~::::::::::~:=::?==============~======~~~~~~=~~~~=======~
====~~~~~~~~I++?I+?????????????????????????????OO::8OOOO=::~::::::::::::::~===+$=+=+==========+++$??$$======~~~~========~~~~=~================+7+~:::::::~:+I::Z7=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~?+???????????????????????????????????7OI:OO::~:::::::::::::::::~====?=============++?8+8????I+?++II$$7?~~~~~~~~~~~~~~=I+=========+IZ===++7~:~7~$7$:,,+?7~~~~~~~~~~~~~~~~~~~::::~~~~~~~~~~~~~~~
~~~~~~~~~+????????+7????????????????????????????8II,::,~::~==~::::::::~=====I===============?OOOO=O??????????????+???7~=~~~~~~~~~~=~?I77?=?===~+======+$I7?,,,:I??+~~~~~~:::~~~~~~~::::::~~~~~~~~~~~~~~~
~~~~~~~~++??????????$+????????????????????????I???+,::,:~==+==?~:~~=====++I+===============+:88OOO:8???????????????????7~~~~~~~~~~~~~~~~~=$I7I=====~7777I,,,::?+??+~~::::::::::::::::::::~~~~~~::::~~~~~
~~~~~~==+????????????Z???????????????????????Z????++,,::,+=+====7=====$?===============+I:~::+88OOO~OI????????????????7??$~~~~~~~~~~~~~~~~$$7777==II7777,:,,~=?????$~:::::::::::::,:::::::~~::::::::~~~~
~~~~~~~++?????????????$????????????????????I???????+?,,:::?============+===========+ZZ$$$:,?:I+OOO8O?8O???????????????+$??I~~~~~~~~:::::::++++======+I~:,,,,=7?+???+7:::,,,:::::,::::::::::::::::::~~~~~
~~~~~~I????????????????$??????????????????$?????????+?,::::=+7=======?I+=+7?7I?:$Z$$OZOOZ$:$:~,7OO888=8O????????????????$+++~~~::::::::::~++++====$==::::::=$????????+::,,::::,,,:::::::::::::::::~~~~~~
~~~~~?+?????????????????7????????????????I???????????++,,::::++$=+======$:$::,:::7Z$$$OOO$$,:,,,8888OO:88???????????????????++::::::::::::=+++OI=+++::::::+7$????????+::::,,,,::::::::::::::::~~~~~~~~~~
~~~~~??????????????????????????????????$??????????????+7:,::=++++$====$7::,=:,,:,:$$$$ZOOZ$$~:,:~8888O8:O8???????????????7????+,::::::::::I+++++++++,::::+I$$I???????+?:,:,,:::::::::::::::~~~~~~~~~~~~~
*/



#include<bits/stdc++.h>
using namespace std;

#define fi              first
#define se                   second
#define ll             long long
#define pb              push_back
#define mp              make_pair
#define pll             pair<ll,ll>
#define vll              vector<int>
#define mll             map<ll,ll>
#define pqg             priority_queue<ll>
#define pqs             priority_queue<ll,vll,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define md             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
const int MAX_CHAR = 256;
void hi()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif
}
void bye()
{
    #ifndef ONLINE_JUDGE
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
    #endif
}
int main() 
{
    ll t;
    cin>>t;
    ll x=t%1000;
    if(x==0)
        cout<<"0";
  
    else
        cout<<1000-x;

    return 0;
}

Measured memory_bytes: 3628