zych1751

#include<bits/stdc++.h>

using namespace std;

int cache[250000];
int arr[250000];

int main()
{
	while(1)

zych1751

#include<bits/stdc++.h>

using namespace std;

int cache[250000];
int arr[250000];

int f(int idx)
{
	if(idx == 0)	return arr[0];

zych1751

#include<bits/stdc++.h>

using namespace std;

char A[1001], B[1001];
int dp[1001][1001];

int main()
{
	scanf("%s", A+1);

zych1751

#include<bits/stdc++.h>

using namespace std;

int n, m;
int arr[100001];
int psum[100001];

int main()
{

zych1751

#include<bits/stdc++.h>

using namespace std;

int n, m;
int arr[1025][1025];
int psum[1025][1025];

int main()
{

zych1751

500000
499999 499997 499995 499993 499991 499989 499987 499985 499983 499981 499979 499977 499975 499973 499971 499969 499967 499965 499963 499961 499959 499957 499955 499953 499951 499949 499947 499945 499943 499941 499939 499937 499935 499933 499931 499929 499927 499925 499923 499921 499919 499917 499915 499913 499911 499909 499907 499905 499903 499901 499899 499897 499895 499893 499891 499889 499887 499885 499883 499881 499879 499877 499875 499873 499871 499869 499867 499865 499863 499861 499859 499857 499855 499853 499851 499849 499847 499845 499843 499841 499839 499837 499835 499833 499831 499829 499827 499825 499823 499821 499819 499817 499815 499813 499811 499809 499807 499805 499803 499801 499799 499797 499795 499793 499791 499789 499787 499785 499783 499781 499779 499777 499775 499773 499771 499769 499767 499765 499763 499761 499759 499757 499755 499753 499751 499749 499747 499745 499743 499741 499739 499737 499735 499733 499731 499729 499727 499725 499723 499721 499719 499717 499715 499713 499711 49

zych1751

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1000000;

struct matrix
{
	long long arr[2][2];

zych1751

#include<bits/stdc++.h>

using namespace std;

int n, m;
int arr[1025][1025];
int psum[1025][1025];

int main()
{

zych1751

#include<bits/stdc++.h>

using namespace std;

int n, m;
int arr[100000];

bool check(int obj)
{
	int l = 0, r = n; // arr[l] <= obj, arr[r] > obj

zych1751

#include<bits/stdc++.h>

using namespace std;

int n, m;
int h[1000000];

bool check(int H)
{
	long long sum = 0;