//Translator is written by Mys_C_K.
#include<bits/stdc++.h>
using namespace std;
#define YXQ_AK_NOIP_2105 ;
#define YXQ_AK_NOIP_2104 !
#define YXQ_AK_NOIP_2103 ^
#define YXQ_AK_NOIP_2102 |
#define YXQ_AK_NOIP_2101 &
#define YXQ_AK_NOIP_2100 ||
#define YXQ_AK_NOIP_2099 &&
#define YXQ_AK_NOIP_2098 >
#define YXQ_AK_NOIP_2097 <
#define YXQ_AK_NOIP_2096 !=
#define YXQ_AK_NOIP_2095 <=
#define YXQ_AK_NOIP_2094 >=
#define YXQ_AK_NOIP_2093 >>
#define YXQ_AK_NOIP_2092 <<
#define YXQ_AK_NOIP_2091 }
#define YXQ_AK_NOIP_2090 {
#define YXQ_AK_NOIP_2089 ]
#define YXQ_AK_NOIP_2088 [
#define YXQ_AK_NOIP_2087 ^=
#define YXQ_AK_NOIP_2086 &=
#define YXQ_AK_NOIP_2085 |=
#define YXQ_AK_NOIP_2084 >>=
#define YXQ_AK_NOIP_2083 <<=
#define YXQ_AK_NOIP_2082 /=
#define YXQ_AK_NOIP_2081 *=
#define YXQ_AK_NOIP_2080 -
#define YXQ_AK_NOIP_2079 -=
#define YXQ_AK_NOIP_2078 --
#define YXQ_AK_NOIP_2077 +
#define YXQ_AK_NOIP_2076 +=
#define YXQ_AK_NOIP_2075 ++
#define YXQ_AK_NOIP_2074 typedef
YXQ_AK_NOIP_2074 long double YXQ_AK_NOIP_2073;
YXQ_AK_NOIP_2074 long long YXQ_AK_NOIP_2072;
#define YXQ_AK_NOIP_2071 else
#define YXQ_AK_NOIP_2070 struct
#define YXQ_AK_NOIP_2069 const
#define YXQ_AK_NOIP_2068 priority_queue
#define YXQ_AK_NOIP_2067 unordered_map
#define YXQ_AK_NOIP_2066 min
#define YXQ_AK_NOIP_2065 inline
#define YXQ_AK_NOIP_2064 return
#define YXQ_AK_NOIP_2063 unsigned
#define YXQ_AK_NOIP_2062 push_back
#define YXQ_AK_NOIP_2061 pair
#define YXQ_AK_NOIP_2060 while
#define YXQ_AK_NOIP_2059 if
#define YXQ_AK_NOIP_2058 upper_bound
#define YXQ_AK_NOIP_2057 delete
#define YXQ_AK_NOIP_2056 memcpy
#define YXQ_AK_NOIP_2055 sizeof
#define YXQ_AK_NOIP_2054 make_pair
#define YXQ_AK_NOIP_2053 queue
#define YXQ_AK_NOIP_2052 namespace
#define YXQ_AK_NOIP_2051 size
#define YXQ_AK_NOIP_2050 second
#define YXQ_AK_NOIP_2049 first
#define YXQ_AK_NOIP_2048 memset
#define YXQ_AK_NOIP_2047 lower_bound
#define YXQ_AK_NOIP_2046 printf
#define YXQ_AK_NOIP_2045 iterator
#define YXQ_AK_NOIP_2044 erase
#define YXQ_AK_NOIP_2043 vector
#define YXQ_AK_NOIP_2042 max
#define YXQ_AK_NOIP_2041 scanf
#define YXQ_AK_NOIP_2040 using
#define YXQ_AK_NOIP_2039 for
#define YXQ_AK_NOIP_2038 sort
#define YXQ_AK_NOIP_2037 false
#define YXQ_AK_NOIP_2036 end
#define YXQ_AK_NOIP_2035 pop
#define YXQ_AK_NOIP_2034 cin
#define YXQ_AK_NOIP_2033 true
#define YXQ_AK_NOIP_2032 find
#define YXQ_AK_NOIP_2031 count
#define YXQ_AK_NOIP_2030 reverse
#define YXQ_AK_NOIP_2029 static
#define YXQ_AK_NOIP_2028 push
#define YXQ_AK_NOIP_2027 endl
#define YXQ_AK_NOIP_2026 unique
#define YXQ_AK_NOIP_2025 empty
#define YXQ_AK_NOIP_2024 begin
#define YXQ_AK_NOIP_2023 insert
#define YXQ_AK_NOIP_2022 cout
#define YXQ_AK_NOIP_2021 std
#define YXQ_AK_NOIP_2020 int
#define YXQ_AK_NOIP_2019 char
#define YXQ_AK_NOIP_2018 swap
#define YXQ_AK_NOIP_2017 new
#define YXQ_AK_NOIP_2016 set
#define YXQ_AK_NOIP_2015 double
#define YXQ_AK_NOIP_2014 map
#define YXQ_AK_NOIP_2013 void
#define YXQ_AK_NOIP_2012 stack
#define YXQ_AK_NOIP_2003 getchar()
#define YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,YXQ_AK_NOIP_2114,YXQ_AK_NOIP_2115) YXQ_AK_NOIP_2039(YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2106=YXQ_AK_NOIP_2114;YXQ_AK_NOIP_2106<=YXQ_AK_NOIP_2115;YXQ_AK_NOIP_2106++)
#define YXQ_AK_NOIP_2005(YXQ_AK_NOIP_2106,v) YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,0,(YXQ_AK_NOIP_2020)v.YXQ_AK_NOIP_2051()-1)
#define YXQ_AK_NOIP_2006(YXQ_AK_NOIP_2114,YXQ_AK_NOIP_2119) YXQ_AK_NOIP_2048(YXQ_AK_NOIP_2114,0,YXQ_AK_NOIP_2055(YXQ_AK_NOIP_2020)*(YXQ_AK_NOIP_2119+1))
#define YXQ_AK_NOIP_2007 YXQ_AK_NOIP_2015
#define YXQ_AK_NOIP_2008 YXQ_AK_NOIP_2062
#define YXQ_AK_NOIP_2009 YXQ_AK_NOIP_2054
#define YXQ_AK_NOIP_2010 YXQ_AK_NOIP_2049
#define YXQ_AK_NOIP_2011 YXQ_AK_NOIP_2050
YXQ_AK_NOIP_2040 YXQ_AK_NOIP_2052 YXQ_AK_NOIP_2021 YXQ_AK_NOIP_2105 
YXQ_AK_NOIP_2074 YXQ_AK_NOIP_2061 YXQ_AK_NOIP_2097 YXQ_AK_NOIP_2020,YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2098  YXQ_AK_NOIP_2001 YXQ_AK_NOIP_2105 
YXQ_AK_NOIP_2074 YXQ_AK_NOIP_2016 YXQ_AK_NOIP_2097 YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2098 ::YXQ_AK_NOIP_2045 YXQ_AK_NOIP_2002 YXQ_AK_NOIP_2105 
YXQ_AK_NOIP_2065 YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2107()
 YXQ_AK_NOIP_2090 
    YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2108,YXQ_AK_NOIP_2109 YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2060((YXQ_AK_NOIP_2109=YXQ_AK_NOIP_2003) YXQ_AK_NOIP_2097 '0' YXQ_AK_NOIP_2100 YXQ_AK_NOIP_2109 YXQ_AK_NOIP_2098 '9') YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2108=YXQ_AK_NOIP_2109 YXQ_AK_NOIP_2103 '0' YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2060((YXQ_AK_NOIP_2109=YXQ_AK_NOIP_2003) YXQ_AK_NOIP_2094 '0' YXQ_AK_NOIP_2099 YXQ_AK_NOIP_2109 YXQ_AK_NOIP_2095 '9')
	    YXQ_AK_NOIP_2108=(YXQ_AK_NOIP_2108 YXQ_AK_NOIP_2092 1) YXQ_AK_NOIP_2077 (YXQ_AK_NOIP_2108 YXQ_AK_NOIP_2092 3) YXQ_AK_NOIP_2077 (YXQ_AK_NOIP_2109 YXQ_AK_NOIP_2103 '0') YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2064 YXQ_AK_NOIP_2108 YXQ_AK_NOIP_2105 
 YXQ_AK_NOIP_2091 
YXQ_AK_NOIP_2069 YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2110=310 YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2053 YXQ_AK_NOIP_2097 YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2098  YXQ_AK_NOIP_2116 YXQ_AK_NOIP_2105 
YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2117 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089 ,YXQ_AK_NOIP_2111 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089 ,YXQ_AK_NOIP_2112 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089 ,YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089 ,YXQ_AK_NOIP_2114 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089 ,YXQ_AK_NOIP_2115 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2110 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2105 
YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2118(YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2108,YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2119,YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2120)
 YXQ_AK_NOIP_2090 
    YXQ_AK_NOIP_2006(YXQ_AK_NOIP_2117,YXQ_AK_NOIP_2120),YXQ_AK_NOIP_2006(YXQ_AK_NOIP_2111,YXQ_AK_NOIP_2120) YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,1,YXQ_AK_NOIP_2119) YXQ_AK_NOIP_2006(YXQ_AK_NOIP_2112 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089 ,YXQ_AK_NOIP_2120),YXQ_AK_NOIP_2117 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2114 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089 =1 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2075  YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2060( YXQ_AK_NOIP_2104 YXQ_AK_NOIP_2116.YXQ_AK_NOIP_2025()) YXQ_AK_NOIP_2116.YXQ_AK_NOIP_2035() YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,1,YXQ_AK_NOIP_2120) YXQ_AK_NOIP_2059(YXQ_AK_NOIP_2117 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2098 YXQ_AK_NOIP_2108) YXQ_AK_NOIP_2116.YXQ_AK_NOIP_2028(YXQ_AK_NOIP_2106),YXQ_AK_NOIP_2111 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089 =1 YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2060( YXQ_AK_NOIP_2104 YXQ_AK_NOIP_2116.YXQ_AK_NOIP_2025())
	 YXQ_AK_NOIP_2090 
	    YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2121=YXQ_AK_NOIP_2116.front() YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2116.YXQ_AK_NOIP_2035() YXQ_AK_NOIP_2105 
	    YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,1,YXQ_AK_NOIP_2119) YXQ_AK_NOIP_2112 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2115 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2121 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2089 =1 YXQ_AK_NOIP_2105 
	    YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,1,YXQ_AK_NOIP_2119)
		 YXQ_AK_NOIP_2090 
		    YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2122=0 YXQ_AK_NOIP_2105 
		    YXQ_AK_NOIP_2060(YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2095 YXQ_AK_NOIP_2120 YXQ_AK_NOIP_2099 YXQ_AK_NOIP_2112 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2089 ) YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2075 ,YXQ_AK_NOIP_2122=1 YXQ_AK_NOIP_2105 
		    YXQ_AK_NOIP_2059(YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2098 YXQ_AK_NOIP_2120) YXQ_AK_NOIP_2064 YXQ_AK_NOIP_2037 YXQ_AK_NOIP_2105 
		    YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2123=YXQ_AK_NOIP_2114 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2113 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2059(YXQ_AK_NOIP_2122) YXQ_AK_NOIP_2117 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2123 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2075  YXQ_AK_NOIP_2105 
		    YXQ_AK_NOIP_2059(YXQ_AK_NOIP_2117 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2123 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2098 YXQ_AK_NOIP_2108 YXQ_AK_NOIP_2099  YXQ_AK_NOIP_2104 YXQ_AK_NOIP_2111 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2123 YXQ_AK_NOIP_2089 ) YXQ_AK_NOIP_2116.YXQ_AK_NOIP_2028(YXQ_AK_NOIP_2123),YXQ_AK_NOIP_2111 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2123 YXQ_AK_NOIP_2089 =1 YXQ_AK_NOIP_2105 
		 YXQ_AK_NOIP_2091 
	 YXQ_AK_NOIP_2091 
    YXQ_AK_NOIP_2064 YXQ_AK_NOIP_2033 YXQ_AK_NOIP_2105 
 YXQ_AK_NOIP_2091 
YXQ_AK_NOIP_2020 main()
 YXQ_AK_NOIP_2090 
    YXQ_AK_NOIP_2020 YXQ_AK_NOIP_2119=YXQ_AK_NOIP_2107(),YXQ_AK_NOIP_2120=YXQ_AK_NOIP_2107(),YXQ_AK_NOIP_2124=1,YXQ_AK_NOIP_2125=YXQ_AK_NOIP_2119,YXQ_AK_NOIP_2126=(YXQ_AK_NOIP_2124 YXQ_AK_NOIP_2077 YXQ_AK_NOIP_2125) YXQ_AK_NOIP_2093 1 YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2004(YXQ_AK_NOIP_2106,1,YXQ_AK_NOIP_2119) YXQ_AK_NOIP_2004(j,1,YXQ_AK_NOIP_2120) YXQ_AK_NOIP_2114 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 j YXQ_AK_NOIP_2089 =YXQ_AK_NOIP_2107(),YXQ_AK_NOIP_2115 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2114 YXQ_AK_NOIP_2088 YXQ_AK_NOIP_2106 YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2088 j YXQ_AK_NOIP_2089  YXQ_AK_NOIP_2089 =j YXQ_AK_NOIP_2105 
    YXQ_AK_NOIP_2060(YXQ_AK_NOIP_2124 YXQ_AK_NOIP_2095 YXQ_AK_NOIP_2125)
	 YXQ_AK_NOIP_2090 
	    YXQ_AK_NOIP_2059(YXQ_AK_NOIP_2118(YXQ_AK_NOIP_2126,YXQ_AK_NOIP_2119,YXQ_AK_NOIP_2120)) YXQ_AK_NOIP_2125=YXQ_AK_NOIP_2126 YXQ_AK_NOIP_2080 1 YXQ_AK_NOIP_2105 
	    YXQ_AK_NOIP_2071 YXQ_AK_NOIP_2124=YXQ_AK_NOIP_2126 YXQ_AK_NOIP_2077 1 YXQ_AK_NOIP_2105 YXQ_AK_NOIP_2126=(YXQ_AK_NOIP_2124 YXQ_AK_NOIP_2077 YXQ_AK_NOIP_2125) YXQ_AK_NOIP_2093 1 YXQ_AK_NOIP_2105 
	 YXQ_AK_NOIP_2091 
    YXQ_AK_NOIP_2064  YXQ_AK_NOIP_2104 YXQ_AK_NOIP_2046("%d\n",YXQ_AK_NOIP_2124) YXQ_AK_NOIP_2105 
 YXQ_AK_NOIP_2091 

Measured memory_bytes: 1408