Submission #870559

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870559	2023-11-08T09:51:27 Z	Lib	Shortcut (IOI16_shortcut)	C++14	100 / 100	1280 ms	186248 KB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
long long lim=1000000000000000000;
long long BoundTopLeft,BoundTopRight,BoundBottomLeft,BoundBottomRight; //Where the lines that forms the current bound cuts the X-axis
long long TopLeft,TopRight,BottomLeft,BottomRight; //Where the lines that forms the current square cuts the Y-axis
int n;
long long Mainline[1000003];
long long Secondline[1000003];
long long Extraline;
long long C,X,Y;
long long Sum[1000003];
long long Diff[1000003];
long long Curmin,CurMaxsum,MaxSumIndex,CurMindiff;
long long TreeDiameter=0;
vector <int> Dominators;
deque <int> MinDiffIndex;
vector <int> TVector;
vector <vector<int> > EnterSquareMakingOrgy;
int P1,P2,P3,P4;
int ok;
struct NewOrder{
	int ID;
	int NextDominatorID;
};
bool operator< (const NewOrder &x, const NewOrder &y){
	return Diff[x.ID]<Diff[y.ID];
}
NewOrder SortedByDiff[1000003];
long long PossibleDiameter(long long Dist){ 
	BoundTopLeft=-lim;
	BoundTopRight=lim;
	BoundBottomLeft=-lim;
	BoundBottomRight=lim;
	int k;
	/*
	From the constrains, it is obvious that we'll now have to finish both the Bound-creating process and checking whether a valid connection exists in O(N) per binary search iteration.
	This means, we'll have to create not too many (precisely no more than 2N) squares, and checking whether a valid connection exists in linear time.
	*/
	
	/*
	From now on, we will refer to Mainline[i]+Secondline[i] as Sum[i] and Mainline[i]-Secondline[i] as Diff[i]
	Notice that not all squares are necessary: As we only cares about the Rightmost TopLeft, Rightmost BottomLeft, Leftmost BottomRight, Leftmost TopRight bound among all squares,
	for all squares that we can create from combining station j with some station i<j (of course they'll have to satisfy Sum[j]-Dist[i]>Dist first), we will only need to care
	about the square with the rightmost TopLeft and the other square with the leftmost BottomRight formed by combining station j with some station i (which is, 2 squares at most for each j)
	(rightmost TopLeft: When we respresent the topleft bound of this square as the graph of x-y=a, this is the one with highest a.
	leftmost BottomRight: Same, but lowest a.
	*/
	//We will handle the "Rightmost TopLeft square" and "Leftmost BottomRight square" quite differently, as creating rightmost squares are a lot easier than creating leftmost squares.
	
	//Phase 1: Creating all Rightmost Topleft squares, and merging them together.
	
	/*
	A "Rightmost Topleft square" formed by station j is the square that is formed by the inequations required for station j to be able to reach station i (i<j), and Sum[j]-Diff[i]>Dist, and 
	the x-y value of the line that overlaps with its TopLeft bound is the highest among all squares formed by station j.
	This square has to satisfy 2 inequations:
	1) Sum[j]-Diff[i]>Dist (so that the square is "valid"
	2) Mainline[j]-(Dist-(Extraline+Secondline[i]+Secondline[j]))-Mainline[i] is max
	<==> Mainline[j]+Secondline[j]-(Mainline[i]-Secondline[i])-Dist+Extraline max
	<==> -(Mainline[i]-Secondline[i]) max <==> (Mainline[i]-Secondline[i]) min (as everything else is fixed - Dist and Exline is given, we are considering a fixed j
	<==> Diff[i] min. Normally we could just calculate Diff[i] normally, but constrain 1) gets in the way. We'll have to check whether the index i with min(Diff[i]) for 1...j-1 also
	satisfies inequation 1 or not.
	But, since that Diff[i] is already a minimum, if Sum[j]-Diff[i] is still <= Dist, there doesn't exist any smaller value of Diff[i], and thus this Sum[i]-Diff[i] is the smallest we'll
	ever get => If it satisfies, cool, take it. Otherwise, there doesn't exist any i that could form a valid square with j, so just skip this j. In the meantime, update the minimum value 
	of Diff accordingly
	*/
	//Determining the prefix minimum of Diff[i] for all i, then proceed to create all Rightmost Topleft square possible
	MinDiffIndex.clear();
	k=1;
	for(int i=1;i<=n;i++){
		if(!MinDiffIndex.empty()){
			k=MinDiffIndex.back();
			C=Dist-(Extraline+Secondline[i]+Secondline[k]);
			X=Mainline[i];
			Y=Mainline[k];
			TopLeft=X-C-Y;
			TopRight=X+C+Y;
			BottomLeft=X-C+Y; 
			BottomRight=X+C-Y; 
			if((Secondline[i]+Secondline[k]+Mainline[i]-Mainline[k])>Dist){
			BoundTopLeft=max(BoundTopLeft,TopLeft);
			BoundTopRight=min(BoundTopRight,TopRight);
			BoundBottomRight=min(BoundBottomRight,BottomRight);
			BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
			}
		}
		if(i==1||Diff[i]<Diff[MinDiffIndex.back()]){
			MinDiffIndex.push_back(i);
		}
	}
	
	//Phase 2: Creating all necessary Leftmost BottomRight squares
	
	/*
	Same as the Rightmost TopLeft squares, but this time those squares are the ones where the lines that overlaps with its BottomRight bounds (which, again, is in the form x-y=a) and a
	as small as possible.
	Constrain inequations: 
	1) Sum[j]-Diff[i]>Dist (so that the square is "valid")
	2) Mainline[j]+(Dist-(Extraline+Secondline[i]+Secondline[j]))-Mainline[i] min
	<==> (Mainline[j]-Secondline[j])-(Mainline[i]+Secondline[i])+Dist-Extraline min
	<==> -(Mainline[i]+Secondline[i]) min (again, everything else is fixed)
	<==> Sum[i] max
	*/
	
	/*
	As the algorithm has to run only O(N) operations per binary search iteration, finding the min-max has to be done in linear time. We should try to find a way to keep the "current minimum
	valid station" or some shit after constantly adding in new stations. From experience, you should be able to tell that we're going to have to use stacks or something combined with some 
	additional property to find the min/max value something something in linear time.
	Notice that: As Sum[j] is increasing, we are getting new candidates for Diff[i], while the old valid indexes of i still satisfies the inequation (if Sum[j]-Diff[i]>Dist, then
	Sum[j]+something that is positive-Diff[i] also has to be >Dist as well). As such, if we only iterate through a certain set of indexes j1,j2,....,jk such that Sum[j1]<Sum[j2]<...<Sum[jk],
	we can keep track of the maximum value of Sum[i] for all valid i, as an already valid i would still be valid for the further Sum[j]s.
	Right now, we're not really sure whether if this works or not, but let's just try to work with it for a minute or two, no?
	
	For a station j, we'll call j a "Dominator" if the value of Sum[j] is the largest out of all values of Sum[a], for 1<=a<=j. (I am not making this up, this is literally what is used by the
	official editorial.) Using the above property, if we only query through only dominators (instead of all stations), we can find the corresponding maximum valid value of Sum[i] in 
	linear time.
	The problem is: Does this even work? Could we guarantee that the Leftmost BottomRight square will always be formed when we "combine" some i and j, such that i<j and j is a dominator? 
	Well, you could go ahead and try to implement it and proof by AC. (spoilers: it does). Here's why.
	
	To proof that the Leftmost BottomRight square will always be the product of combining a dominator j with some valid i, we'll have to think very much backwards. This time, instead of fixing
	the value of j, we will have to fix the value of i instead.
	Let's look at our 2nd constrain inequation again: (Mainline[j]-Secondline[j])-(Mainline[i]+Secondline[i])+Dist-Extraline is min. As everything else is locked, we have:
	(Mainline[j]-Secondline[j]) has to be min. 
	We now have:
	Mainline[j] is max of all values of Mainline[k] for all 1<=k<=j => 2*Mainline[j] is max of all values of 2*Mainline[k] for all 1<=k<=j 
	Diff[j] is min of all values of Diff[k] for all 1<=k<=j
	=> 2*Mainline[j]-(Mainline[j]-Secondline[j]) is max of 2*Mainline[k]-(Mainline[k]-Secondline[k]) for all 1<=k<=j
	=> Mainline[j]+Secondline[j]=Sum[j] is max of Sum[k] for all 1<=k<=j
	=> By definition, station j is a Dominator
	=> If we can create a valid Leftmost BottomRight square by combining station i and some j>i, station j has to be a dominator
	=> Checking only Dominators will still guarantee to find the Leftmost BottomRight square
	*/
	
	/*
	As such, we can do the following to determine the Leftmost BottomRight square:
	Step 1: Determining all Dominators.
	Step 2: While transitioning from a Dominator to the next one, update the set of new valid candidates for i, and change the current maximum value of Sum[i] accordingly
	Step 3: Now, create the Leftmost BottomRight square that could be created from this Dominator. Update the bounds accordingly. Move on to the next Dominator 
	Step 1 and 3 is literally trivial, but step 2 is quite a bit troublesome. Finding the largest value of Sum[i] that satisfies requires a little bit of extra work. Like, 30 lines of code
	or something.
	When moving from a dominator to the next, it's not guaranteed that all stations in between will be valid (see: Sample input 2: Moving from the 2nd dominator (at station 2) to the 3rd 
	dominator (at station 6), there aren't any squares formed by station 3 yet. It takes until we started considering the 4th dominator (at station 8) for any squares featuring station 3
	to be formed
	=> We'll have to determine the first dominator j that could make a valid square when combined with station i. All later dominators would be able to create squares with station i
	(look at why we even started considering only dominators as the larger value in a pair of indexes that forms a square in the first place).
	
	Now, we call station i "submissive and breedable" to station j if the following 2 conditions hold:
	- i is dominated by j (or: i<j and station j is a dominator)
	- Sum[j]-Diff[i]>Dist (so that it could "breed" a square)
	As we're iterating through dominators (read: in order of increasing Sum[j], the maximum value for Diff[i] that could "breed" a square is constantly increasing. Which means, assuming
	if we tempolarily ditch the 1st condition entirely, if we sort the indexes in order of increasing Diff[i], we can constantly update the set of "valid" indicies after moving into 
	a new dominator simply by moving the bound closer to the end of the sorted array
	=>....Yeah, just sort everything (in a secondary array) and try to work with it and overcome the 1st condition
	
	Now, scroll down for the sorting part (line 324)
	*/
	k=1;
	/*
	EnterSquareMakingOrgy[i]: The set of indexes that is made submissive and breedable by the i-th dominator. When we get to the i-th dominator, we allow all of the indexes in this stack to
	"get" into the "these indexes could make valid squares" set (or, quite literally, let them enter the "square making orgy") and then update the max value of valid Sum[i] accordingly.
	This is (probably) not a joke.
	*/
	CurMaxsum=-lim;
	int Pointer=1;
	MaxSumIndex=1;
	//BIG MISTAKE: DO NOT start from 1. Like, wtf is the first fucking station even going to dominate? (unless it is into selfcest. that is still not a thing in this task though
	//So, yeah, start from the 2nd dominator. Don't waste an hour trying to debug (like I did) (actually only 5 minutes)
	for(int i=2;i<Dominators.size();i++){
		/*
		Now, when will station i be both submissive AND breedable entirely to station j? When station i is dominated by station j, and station i is breedable by station j, of course
		First dominator that makes i submissive: ID of the dominator assigned to station i = A. 
		First Dominator that makes i breedable: ID of the dominator we're considering right now = B. We say that i is primarily made breedable by the B-th dominator
		First Dominator that makes i both submissive AND breedable: First station that satisfy both conditions aka max(A,B), lol
		*/
		while(Pointer<=n&&Sum[Dominators[i]]-Diff[SortedByDiff[Pointer].ID]>Dist){
			//This is the list of all stations made breedable primarily by the i-th dominator
			EnterSquareMakingOrgy[max(i,SortedByDiff[Pointer].NextDominatorID)].push_back(SortedByDiff[Pointer].ID);
				Pointer++;
		}
		//Allowing the stations made submissive and breedable by i-th dominator into the "valid" set/square making orgy. Updating the value of current max valid Sum
		while(!EnterSquareMakingOrgy[i].empty()){
			if(CurMaxsum<Sum[EnterSquareMakingOrgy[i].back()]){
				CurMaxsum=Sum[EnterSquareMakingOrgy[i].back()];
				MaxSumIndex=EnterSquareMakingOrgy[i].back();
			}
			EnterSquareMakingOrgy[i].pop_back();
		}
		//Make the corresponding Leftmost BottomRight square
			k=MaxSumIndex;
			C=Dist-(Extraline+Secondline[Dominators[i]]+Secondline[k]);
			X=Mainline[Dominators[i]];
			Y=Mainline[k];
			TopLeft=X-C-Y;
			TopRight=X+C+Y;
			BottomLeft=X-C+Y; 
			BottomRight=X+C-Y; 
			if((Secondline[Dominators[i]]+Secondline[k]+Mainline[Dominators[i]]-Mainline[k])>Dist){
			BoundTopLeft=max(BoundTopLeft,TopLeft);
			BoundTopRight=min(BoundTopRight,TopRight);
			BoundBottomRight=min(BoundBottomRight,BottomRight);
			BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
			}
	}
	while(!EnterSquareMakingOrgy[1].empty()){
			EnterSquareMakingOrgy[1].pop_back();
		}
	if(BoundTopLeft>BoundBottomRight||BoundBottomLeft>BoundTopRight){
		return 0;
	}
	//Phase 3: Checking whether there is a pair of stations (i,j) that is valid (a "solution" to all inequations formed by the squares, in O(N)
	
	/*
	For every single point formed by considering a pair of station (i,j), we have: (Coordinate of that point)=(Mainline[j],Mainline[i])
	For each point, there is an unique pair of lines Y=X-A and Y=X-B that goes through it (as, given the sum and difference of 2 numbers, we could find a single pair
	of numbers that satisfies both equations)
	Now, the conditions for a point (x,y) to be inside the intersection of all squares would be equal to:
	BoundTopLeft <= X-Y <= BoundBottomRight
	BoundBottomLeft <= X+Y <= BoundTopRight
	
	Now, when we consider station i and j (with j>i),we can now modify the inequations to:
	BoundTopLeft <= Mainline[j]-Mainline[i] <= BoundBottomRight
	BoundBottomLeft<= Mainline[j]+Mainline[i] <= BoundTopRight
	As we iterate through dominator j in increasing order, we notice that:
	- The indexes of i that satisfies the first inequation will constantly move towards the end of the list of stations when j increases
	- The indexes of i that satisfies the second inequation will constantly move towards the beginning of the list of stations as j increases
	- If those 2 ranges intersects at at least 1 station for a certain i, we know for sure that this pair of stations of (j,the intersection) satisfies both inequations,
	and is inside the "bound", and the answer is valid
	=> Just use 4 pointers, 2 for managing the range of indexes that satisfy the 1st inequation, 2 for the 2nd inequation
	*/
	P1=1;
	P2=n+1;
	P3=1;
	P4=n+1;
	ok=0;
	/*
	While two-pointers are very simple, do not underestimate it (your skill issue, to be precise). My dumb ass spent 2 hour trying to iterate through only dominators as endpoint of the shortcut
	and wondering why tf doesn't it work out, lol.
	Reminder: Optimal squares are only created with dominators as endpoint, Shortcut can be between whatever.
	ALso, you'll kinda have to "prepare" beforehand: Calculate where the bounds end up for i=1, then move the bounds accordingly. Otherwise, you'll waste
	4 hours for something supposedly trivial like 2-pointers. Definitely funny.
	......also remember what each bound stands for as well. Dumb fucker forgot that we are only considering pairs of stations (j,i) (with j>i) and not the
	other way around, proceed to debug for 5 fucking hours not understanding why the code managed to fuck up so bad. To think that it still pass 50% of the 
	tests.......
	(check the standard i/o version of this task on dmoj.ca to see the funny)
	*/
	//For the initialization (working with Mainline[1], it is 0, so I leave it out 
	while(Mainline[P1]<BoundTopLeft&&P1<=n){
		P1++;
	}
	while(Mainline[P3]<BoundBottomLeft&&P3<=n){
		P3++;
	}
	while(Mainline[P2]>BoundBottomRight&&P2>1){
		P2--;
	}
	while(Mainline[P4]>BoundTopRight&&P4>1){
		P4--;
	}
	 if(P1<=P2&&P3<=P4){
	    //Checking whether the 2 ranges intersects
	    if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
	        ok=1;
	        return ok;
	    }
		}
	for(int i=2;i<=n;i++){
	    while(Mainline[P1]-Mainline[i]<BoundTopLeft&&P1<=n){
	        P1++;
	    }
	    while(Mainline[P2+1]-Mainline[i]<=BoundBottomRight&&P2<=n){
	        P2++;
	    }
	    while(Mainline[i]+Mainline[P3-1]>=BoundBottomLeft&&P3>1){
	        P3--;
	    }
	    while(Mainline[i]+Mainline[P4]>BoundTopRight&&P4>=1){
	        P4--;
	    }
	    //Can't create a station with either the 1st range or 2nd range not being valid, or if there is no valid range at all
	    //Example: if the change from Mainline[i] to Mainline[i+1] is too sudden, it is possible for the range [BoundTopLeft,BoundBottomRight] to be skipped over entirely, so there is station
	    //that could create a satisfying shortcut
	    if(P1<=P2&&P3<=P4){
	    //Checking whether the 2 ranges intersects
	    if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
	        ok=1;
	        return ok;
	    }
		}
	}
		return ok;
}
long long find_shortcut(int N, vector <int> L, vector <int> D, int C){
	n=N;
	Extraline=C;
	long long temp=0;
	for(int i=2;i<=n;i++){
		temp=L[i-2];
		Mainline[i]=Mainline[i-1]+temp;
	}
	Mainline[n+1]=lim;
	//For utility later
	Curmin=lim;
	CurMindiff=lim;
	for(int i=1;i<=n;i++){
		Secondline[i]=D[i-1];
		Sum[i]=Mainline[i]+Secondline[i];
		Diff[i]=Mainline[i]-Secondline[i];
		if(i>=2){
			TreeDiameter=max(TreeDiameter,Sum[i]-CurMindiff);
			//Let Mainline Station 1 be the "root" of the network (yeah, it is a tree, how could you tell
			//Distance between Secondline station i and Secondline station j = Mainline[i]-Mainline[j]+Secondline[i]+Secondline[j]
			// = (Mainline[i]+Secondline[i])-(Mainline[j]-Secondline[j]).
			//Thus, the greatest distance between Secondline station i and some Secondline station j before station i is with a station j with the smallest value of (Mainline[j]-Secondline[j]).
			//The largest value of Dist(Secondline station i, Secondline station j) over all i is the tree diameter.
		}
		CurMindiff=min(CurMindiff,Diff[i]);
	}
	long long l=1,r=TreeDiameter;
	//No reason to search for any answer larger than the diameter of the tree - if adding a segment makes the answer larger than just using the base network, why even bother
	
	//Now, look at the explaination for the PossibleDiameter function first, before looking at this next sorting part. (line 30)
	
	/*
	Okay, now we're back to the sorting part again.
	By combining the 2 restrictions, it is obvious what we should care about in order to make station i submissive and breedable:
	- The first dominator that dominates station i (the closest dominator to the right of station i)
	- The index of station i itself - which would then be used to determine the value of Diff[i], and thus determine the first dominator that makes station i breedable
	
	We only need to sort once though, as the only thing that matters is the order of values of Diff[i]. Other things might be different between different values of Dist, but this array
	still works the same
	*/
	Dominators.clear();
	Dominators.push_back(0);
	EnterSquareMakingOrgy.clear();
	//Determining Dominators, thus finding the ID of the immediate next dominator from station i (ex:ID=3 means the 3rd dominator is the first dominator to the right of station i
	for(int i=1;i<=n;i++){
		if(Sum[i]>Sum[Dominators.back()]){
			Dominators.push_back(i);
		}
		SortedByDiff[i]={i,Dominators.size()};
	}
	for(int i=0;i<=Dominators.size()+1;i++){
		EnterSquareMakingOrgy.push_back(TVector);
	}
	//The questionable name is for...later uses
	sort(SortedByDiff+1,SortedByDiff+n+1);
	//Okay, now back to the top again (line 30)
	long long mid;
	while(r-l>1){
		mid=(r+l)/2;
		if(PossibleDiameter(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(PossibleDiameter(l)){
		return l;
	}else if(PossibleDiameter(r)){
		return r;
	}
}
/*
Post-AC comments:
- What kind of demon made this shit? Like, unironically. What? Why? How? 
- While the 71pts algorithm is fairly easy (the 97pts one requires slapping segtree into the thing and call it a day), the last 3 points requires 2 more
observations (and with it, 2 proofs), potentially pain-inducing 4-pointers. 71pts algorithm took me 2 hour of drafting to come up and another 2 hour to implement.
This piece of shit took 10 days out of my life, at least 6 pages of inequations and random proof. What the actual fuck
- Note to self: Vectors are far better than stack. Took an hour to avoid the dreaded Signal 9 by trying different things, and only got AC when swapped from 
stack to vector. Cool. TIL that the kind of data structure actually matters.

....now that I'm done with this, I could have a life again
*/

Compilation message

shortcut.cpp: In function 'long long int PossibleDiameter(long long int)':
shortcut.cpp:168:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |  for(int i=2;i<Dominators.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:340:37: warning: narrowing conversion of 'Dominators.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  340 |   SortedByDiff[i]={i,Dominators.size()};
      |                      ~~~~~~~~~~~~~~~^~
shortcut.cpp:342:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  342 |  for(int i=0;i<=Dominators.size()+1;i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~
shortcut.cpp:362:1: warning: control reaches end of non-void function [-Wreturn-type]
  362 | }
      | ^

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
73	Correct	1 ms	8540 KB	n = 250, 25037 is a correct answer
74	Correct	1 ms	8540 KB	n = 250, 199047242 is a correct answer
75	Correct	1 ms	8540 KB	n = 250, 61231537449 is a correct answer
76	Correct	1 ms	8540 KB	n = 250, 126000000001 is a correct answer
77	Correct	2 ms	8540 KB	n = 250, 127000000000 is a correct answer
78	Correct	2 ms	8540 KB	n = 250, 2123470094 is a correct answer
79	Correct	1 ms	8628 KB	n = 250, 6545 is a correct answer
80	Correct	1 ms	8540 KB	n = 250, 6731 is a correct answer
81	Correct	1 ms	8536 KB	n = 108, 15322 is a correct answer
82	Correct	1 ms	8536 KB	n = 250, 39952 is a correct answer
83	Correct	1 ms	8540 KB	n = 250, 41156 is a correct answer
84	Correct	1 ms	8540 KB	n = 250, 12881 is a correct answer
85	Correct	1 ms	8540 KB	n = 250, 213812 is a correct answer
86	Correct	1 ms	8540 KB	n = 250, 194188 is a correct answer

Subtask #4

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
73	Correct	1 ms	8540 KB	n = 250, 25037 is a correct answer
74	Correct	1 ms	8540 KB	n = 250, 199047242 is a correct answer
75	Correct	1 ms	8540 KB	n = 250, 61231537449 is a correct answer
76	Correct	1 ms	8540 KB	n = 250, 126000000001 is a correct answer
77	Correct	2 ms	8540 KB	n = 250, 127000000000 is a correct answer
78	Correct	2 ms	8540 KB	n = 250, 2123470094 is a correct answer
79	Correct	1 ms	8628 KB	n = 250, 6545 is a correct answer
80	Correct	1 ms	8540 KB	n = 250, 6731 is a correct answer
81	Correct	1 ms	8536 KB	n = 108, 15322 is a correct answer
82	Correct	1 ms	8536 KB	n = 250, 39952 is a correct answer
83	Correct	1 ms	8540 KB	n = 250, 41156 is a correct answer
84	Correct	1 ms	8540 KB	n = 250, 12881 is a correct answer
85	Correct	1 ms	8540 KB	n = 250, 213812 is a correct answer
86	Correct	1 ms	8540 KB	n = 250, 194188 is a correct answer
87	Correct	1 ms	8540 KB	n = 500, 199300822 is a correct answer
88	Correct	1 ms	8540 KB	n = 500, 127613044387 is a correct answer
89	Correct	1 ms	8540 KB	n = 500, 251000000001 is a correct answer
90	Correct	1 ms	8540 KB	n = 500, 252000000000 is a correct answer
91	Correct	1 ms	8540 KB	n = 500, 199378978 is a correct answer
92	Correct	1 ms	8540 KB	n = 500, 199551149 is a correct answer
93	Correct	1 ms	8540 KB	n = 400, 7177 is a correct answer
94	Correct	1 ms	8540 KB	n = 400, 10067 is a correct answer
95	Correct	1 ms	8536 KB	n = 500, 198631068 is a correct answer
96	Correct	1 ms	8540 KB	n = 400, 10814 is a correct answer
97	Correct	1 ms	8540 KB	n = 400, 9141 is a correct answer
98	Correct	2 ms	8540 KB	n = 500, 5699 is a correct answer
99	Correct	1 ms	8540 KB	n = 500, 13504 is a correct answer
100	Correct	1 ms	8540 KB	n = 500, 31507 is a correct answer
101	Correct	1 ms	8540 KB	n = 500, 199425296 is a correct answer
102	Correct	1 ms	8540 KB	n = 500, 198990259 is a correct answer
103	Correct	1 ms	8536 KB	n = 500, 486155 is a correct answer
104	Correct	1 ms	8536 KB	n = 500, 256468 is a correct answer
105	Correct	1 ms	8540 KB	n = 500, 309873 is a correct answer
106	Correct	1 ms	8540 KB	n = 500, 434764 is a correct answer

Subtask #5

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
73	Correct	1 ms	8540 KB	n = 250, 25037 is a correct answer
74	Correct	1 ms	8540 KB	n = 250, 199047242 is a correct answer
75	Correct	1 ms	8540 KB	n = 250, 61231537449 is a correct answer
76	Correct	1 ms	8540 KB	n = 250, 126000000001 is a correct answer
77	Correct	2 ms	8540 KB	n = 250, 127000000000 is a correct answer
78	Correct	2 ms	8540 KB	n = 250, 2123470094 is a correct answer
79	Correct	1 ms	8628 KB	n = 250, 6545 is a correct answer
80	Correct	1 ms	8540 KB	n = 250, 6731 is a correct answer
81	Correct	1 ms	8536 KB	n = 108, 15322 is a correct answer
82	Correct	1 ms	8536 KB	n = 250, 39952 is a correct answer
83	Correct	1 ms	8540 KB	n = 250, 41156 is a correct answer
84	Correct	1 ms	8540 KB	n = 250, 12881 is a correct answer
85	Correct	1 ms	8540 KB	n = 250, 213812 is a correct answer
86	Correct	1 ms	8540 KB	n = 250, 194188 is a correct answer
87	Correct	1 ms	8540 KB	n = 500, 199300822 is a correct answer
88	Correct	1 ms	8540 KB	n = 500, 127613044387 is a correct answer
89	Correct	1 ms	8540 KB	n = 500, 251000000001 is a correct answer
90	Correct	1 ms	8540 KB	n = 500, 252000000000 is a correct answer
91	Correct	1 ms	8540 KB	n = 500, 199378978 is a correct answer
92	Correct	1 ms	8540 KB	n = 500, 199551149 is a correct answer
93	Correct	1 ms	8540 KB	n = 400, 7177 is a correct answer
94	Correct	1 ms	8540 KB	n = 400, 10067 is a correct answer
95	Correct	1 ms	8536 KB	n = 500, 198631068 is a correct answer
96	Correct	1 ms	8540 KB	n = 400, 10814 is a correct answer
97	Correct	1 ms	8540 KB	n = 400, 9141 is a correct answer
98	Correct	2 ms	8540 KB	n = 500, 5699 is a correct answer
99	Correct	1 ms	8540 KB	n = 500, 13504 is a correct answer
100	Correct	1 ms	8540 KB	n = 500, 31507 is a correct answer
101	Correct	1 ms	8540 KB	n = 500, 199425296 is a correct answer
102	Correct	1 ms	8540 KB	n = 500, 198990259 is a correct answer
103	Correct	1 ms	8536 KB	n = 500, 486155 is a correct answer
104	Correct	1 ms	8536 KB	n = 500, 256468 is a correct answer
105	Correct	1 ms	8540 KB	n = 500, 309873 is a correct answer
106	Correct	1 ms	8540 KB	n = 500, 434764 is a correct answer
107	Correct	3 ms	8540 KB	n = 3000, 2002090624 is a correct answer
108	Correct	2 ms	8540 KB	n = 3000, 2000061654 is a correct answer
109	Correct	2 ms	8540 KB	n = 3000, 2000932313 is a correct answer
110	Correct	2 ms	8540 KB	n = 3000, 2284734775 is a correct answer
111	Correct	2 ms	8540 KB	n = 3000, 2000005545 is a correct answer
112	Correct	2 ms	8536 KB	n = 3000, 2000058220 is a correct answer
113	Correct	2 ms	8700 KB	n = 3000, 2004740516 is a correct answer
114	Correct	3 ms	8796 KB	n = 3000, 909698 is a correct answer
115	Correct	2 ms	8540 KB	n = 3000, 2706266 is a correct answer
116	Correct	2 ms	8540 KB	n = 3000, 2707838 is a correct answer
117	Correct	2 ms	8536 KB	n = 3000, 2829769 is a correct answer
118	Correct	2 ms	8540 KB	n = 3000, 1998685638 is a correct answer
119	Correct	3 ms	8796 KB	n = 3000, 746571 is a correct answer
120	Correct	2 ms	8540 KB	n = 3000, 2744243 is a correct answer
121	Correct	2 ms	8540 KB	n = 3000, 2702210935 is a correct answer
122	Correct	3 ms	8824 KB	n = 3000, 1501000000001 is a correct answer
123	Correct	4 ms	8796 KB	n = 3000, 1502000000000 is a correct answer
124	Correct	2 ms	8540 KB	n = 3000, 2000011887 is a correct answer
125	Correct	2 ms	8540 KB	n = 3000, 2000000012 is a correct answer
126	Correct	2 ms	8540 KB	n = 3000, 2000014932 is a correct answer
127	Correct	2 ms	8796 KB	n = 3000, 2000000010 is a correct answer
128	Correct	2 ms	8540 KB	n = 3000, 93337 is a correct answer
129	Correct	3 ms	8540 KB	n = 3000, 35741 is a correct answer
130	Correct	2 ms	8536 KB	n = 3000, 1999093518 is a correct answer
131	Correct	4 ms	8796 KB	n = 3000, 762334538894 is a correct answer
132	Correct	2 ms	8540 KB	n = 3000, 94081666 is a correct answer
133	Correct	3 ms	8796 KB	n = 3000, 75872047 is a correct answer
134	Correct	3 ms	8796 KB	n = 3000, 3070594 is a correct answer
135	Correct	3 ms	9052 KB	n = 3000, 3003076 is a correct answer
136	Correct	2 ms	8540 KB	n = 3000, 3010050 is a correct answer
137	Correct	2 ms	9048 KB	n = 3000, 1497758 is a correct answer
138	Correct	3 ms	8796 KB	n = 3000, 3025965 is a correct answer
139	Correct	3 ms	8936 KB	n = 3000, 2946044 is a correct answer
140	Correct	2 ms	8540 KB	n = 3000, 2992056 is a correct answer
141	Correct	3 ms	8916 KB	n = 3000, 1490827 is a correct answer
142	Correct	2 ms	8540 KB	n = 3000, 1477754 is a correct answer
143	Correct	2 ms	8540 KB	n = 3000, 2412238 is a correct answer
144	Correct	2 ms	8540 KB	n = 3000, 2742628 is a correct answer
145	Correct	2 ms	8664 KB	n = 3000, 4480584 is a correct answer
146	Correct	2 ms	8792 KB	n = 3000, 4219917 is a correct answer
147	Correct	2 ms	8540 KB	n = 3000, 4207852 is a correct answer
148	Correct	2 ms	8540 KB	n = 3000, 2414542 is a correct answer
149	Correct	2 ms	8540 KB	n = 3000, 1120350 is a correct answer

Subtask #6

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
73	Correct	1 ms	8540 KB	n = 250, 25037 is a correct answer
74	Correct	1 ms	8540 KB	n = 250, 199047242 is a correct answer
75	Correct	1 ms	8540 KB	n = 250, 61231537449 is a correct answer
76	Correct	1 ms	8540 KB	n = 250, 126000000001 is a correct answer
77	Correct	2 ms	8540 KB	n = 250, 127000000000 is a correct answer
78	Correct	2 ms	8540 KB	n = 250, 2123470094 is a correct answer
79	Correct	1 ms	8628 KB	n = 250, 6545 is a correct answer
80	Correct	1 ms	8540 KB	n = 250, 6731 is a correct answer
81	Correct	1 ms	8536 KB	n = 108, 15322 is a correct answer
82	Correct	1 ms	8536 KB	n = 250, 39952 is a correct answer
83	Correct	1 ms	8540 KB	n = 250, 41156 is a correct answer
84	Correct	1 ms	8540 KB	n = 250, 12881 is a correct answer
85	Correct	1 ms	8540 KB	n = 250, 213812 is a correct answer
86	Correct	1 ms	8540 KB	n = 250, 194188 is a correct answer
87	Correct	1 ms	8540 KB	n = 500, 199300822 is a correct answer
88	Correct	1 ms	8540 KB	n = 500, 127613044387 is a correct answer
89	Correct	1 ms	8540 KB	n = 500, 251000000001 is a correct answer
90	Correct	1 ms	8540 KB	n = 500, 252000000000 is a correct answer
91	Correct	1 ms	8540 KB	n = 500, 199378978 is a correct answer
92	Correct	1 ms	8540 KB	n = 500, 199551149 is a correct answer
93	Correct	1 ms	8540 KB	n = 400, 7177 is a correct answer
94	Correct	1 ms	8540 KB	n = 400, 10067 is a correct answer
95	Correct	1 ms	8536 KB	n = 500, 198631068 is a correct answer
96	Correct	1 ms	8540 KB	n = 400, 10814 is a correct answer
97	Correct	1 ms	8540 KB	n = 400, 9141 is a correct answer
98	Correct	2 ms	8540 KB	n = 500, 5699 is a correct answer
99	Correct	1 ms	8540 KB	n = 500, 13504 is a correct answer
100	Correct	1 ms	8540 KB	n = 500, 31507 is a correct answer
101	Correct	1 ms	8540 KB	n = 500, 199425296 is a correct answer
102	Correct	1 ms	8540 KB	n = 500, 198990259 is a correct answer
103	Correct	1 ms	8536 KB	n = 500, 486155 is a correct answer
104	Correct	1 ms	8536 KB	n = 500, 256468 is a correct answer
105	Correct	1 ms	8540 KB	n = 500, 309873 is a correct answer
106	Correct	1 ms	8540 KB	n = 500, 434764 is a correct answer
107	Correct	3 ms	8540 KB	n = 3000, 2002090624 is a correct answer
108	Correct	2 ms	8540 KB	n = 3000, 2000061654 is a correct answer
109	Correct	2 ms	8540 KB	n = 3000, 2000932313 is a correct answer
110	Correct	2 ms	8540 KB	n = 3000, 2284734775 is a correct answer
111	Correct	2 ms	8540 KB	n = 3000, 2000005545 is a correct answer
112	Correct	2 ms	8536 KB	n = 3000, 2000058220 is a correct answer
113	Correct	2 ms	8700 KB	n = 3000, 2004740516 is a correct answer
114	Correct	3 ms	8796 KB	n = 3000, 909698 is a correct answer
115	Correct	2 ms	8540 KB	n = 3000, 2706266 is a correct answer
116	Correct	2 ms	8540 KB	n = 3000, 2707838 is a correct answer
117	Correct	2 ms	8536 KB	n = 3000, 2829769 is a correct answer
118	Correct	2 ms	8540 KB	n = 3000, 1998685638 is a correct answer
119	Correct	3 ms	8796 KB	n = 3000, 746571 is a correct answer
120	Correct	2 ms	8540 KB	n = 3000, 2744243 is a correct answer
121	Correct	2 ms	8540 KB	n = 3000, 2702210935 is a correct answer
122	Correct	3 ms	8824 KB	n = 3000, 1501000000001 is a correct answer
123	Correct	4 ms	8796 KB	n = 3000, 1502000000000 is a correct answer
124	Correct	2 ms	8540 KB	n = 3000, 2000011887 is a correct answer
125	Correct	2 ms	8540 KB	n = 3000, 2000000012 is a correct answer
126	Correct	2 ms	8540 KB	n = 3000, 2000014932 is a correct answer
127	Correct	2 ms	8796 KB	n = 3000, 2000000010 is a correct answer
128	Correct	2 ms	8540 KB	n = 3000, 93337 is a correct answer
129	Correct	3 ms	8540 KB	n = 3000, 35741 is a correct answer
130	Correct	2 ms	8536 KB	n = 3000, 1999093518 is a correct answer
131	Correct	4 ms	8796 KB	n = 3000, 762334538894 is a correct answer
132	Correct	2 ms	8540 KB	n = 3000, 94081666 is a correct answer
133	Correct	3 ms	8796 KB	n = 3000, 75872047 is a correct answer
134	Correct	3 ms	8796 KB	n = 3000, 3070594 is a correct answer
135	Correct	3 ms	9052 KB	n = 3000, 3003076 is a correct answer
136	Correct	2 ms	8540 KB	n = 3000, 3010050 is a correct answer
137	Correct	2 ms	9048 KB	n = 3000, 1497758 is a correct answer
138	Correct	3 ms	8796 KB	n = 3000, 3025965 is a correct answer
139	Correct	3 ms	8936 KB	n = 3000, 2946044 is a correct answer
140	Correct	2 ms	8540 KB	n = 3000, 2992056 is a correct answer
141	Correct	3 ms	8916 KB	n = 3000, 1490827 is a correct answer
142	Correct	2 ms	8540 KB	n = 3000, 1477754 is a correct answer
143	Correct	2 ms	8540 KB	n = 3000, 2412238 is a correct answer
144	Correct	2 ms	8540 KB	n = 3000, 2742628 is a correct answer
145	Correct	2 ms	8664 KB	n = 3000, 4480584 is a correct answer
146	Correct	2 ms	8792 KB	n = 3000, 4219917 is a correct answer
147	Correct	2 ms	8540 KB	n = 3000, 4207852 is a correct answer
148	Correct	2 ms	8540 KB	n = 3000, 2414542 is a correct answer
149	Correct	2 ms	8540 KB	n = 3000, 1120350 is a correct answer
150	Correct	21 ms	12124 KB	n = 50000, 2000049546 is a correct answer
151	Correct	48 ms	15696 KB	n = 100000, 848578639 is a correct answer
152	Correct	49 ms	19528 KB	n = 100000, 50051 is a correct answer
153	Correct	43 ms	16080 KB	n = 100000, 1999983977 is a correct answer
154	Correct	113 ms	19532 KB	n = 100000, 25012377121147 is a correct answer
155	Correct	110 ms	19372 KB	n = 100000, 24945762330734 is a correct answer
156	Correct	47 ms	15540 KB	n = 100000, 2742000148 is a correct answer
157	Correct	42 ms	15696 KB	n = 100000, 3193426460 is a correct answer
158	Correct	48 ms	15740 KB	n = 100000, 2752140525 is a correct answer
159	Correct	39 ms	15852 KB	n = 100000, 2495802167 is a correct answer
160	Correct	89 ms	19788 KB	n = 100000, 50001000000001 is a correct answer
161	Correct	87 ms	20044 KB	n = 100000, 50002000000000 is a correct answer
162	Correct	39 ms	15588 KB	n = 99999, 2000099997 is a correct answer
163	Correct	39 ms	16976 KB	n = 100000, 2000000559 is a correct answer
164	Correct	33 ms	16340 KB	n = 100000, 2075040000 is a correct answer
165	Correct	38 ms	15708 KB	n = 100000, 2749569701 is a correct answer
166	Correct	39 ms	15800 KB	n = 100000, 2749883772 is a correct answer
167	Correct	37 ms	15832 KB	n = 100000, 1996399503 is a correct answer
168	Correct	45 ms	20304 KB	n = 100000, 945722555 is a correct answer
169	Correct	74 ms	19624 KB	n = 100000, 100172188 is a correct answer
170	Correct	60 ms	26552 KB	n = 100000, 150030536 is a correct answer
171	Correct	33 ms	15184 KB	n = 100000, 100040142 is a correct answer
172	Correct	54 ms	21068 KB	n = 100000, 74983555 is a correct answer
173	Correct	74 ms	20136 KB	n = 100000, 99749623 is a correct answer
174	Correct	76 ms	26684 KB	n = 100000, 150054317 is a correct answer
175	Correct	36 ms	15828 KB	n = 100000, 100165316 is a correct answer
176	Correct	52 ms	17944 KB	n = 100000, 75200683 is a correct answer
177	Correct	36 ms	16280 KB	n = 100000, 677987385 is a correct answer
178	Correct	40 ms	15832 KB	n = 100000, 1892389617 is a correct answer
179	Correct	38 ms	15552 KB	n = 100000, 2023768088 is a correct answer
180	Correct	36 ms	15452 KB	n = 100000, 2064255369 is a correct answer
181	Correct	37 ms	15440 KB	n = 100000, 2071899482 is a correct answer
182	Correct	44 ms	15188 KB	n = 100000, 2006764926 is a correct answer
183	Correct	40 ms	15708 KB	n = 100000, 2010002796 is a correct answer
184	Correct	35 ms	15196 KB	n = 100000, 1985971897 is a correct answer
185	Correct	46 ms	15780 KB	n = 100000, 1991354990 is a correct answer
186	Correct	48 ms	15752 KB	n = 100000, 252662746 is a correct answer
187	Correct	47 ms	15996 KB	n = 100000, 251359741 is a correct answer
188	Correct	46 ms	15864 KB	n = 100000, 252831309 is a correct answer
189	Correct	47 ms	16000 KB	n = 100000, 257146653 is a correct answer
190	Correct	34 ms	16104 KB	n = 100000, 501262012 is a correct answer
191	Correct	78 ms	26176 KB	n = 100000, 83054154 is a correct answer
192	Correct	41 ms	15828 KB	n = 100000, 68547208 is a correct answer

Subtask #7

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
73	Correct	1 ms	8540 KB	n = 250, 25037 is a correct answer
74	Correct	1 ms	8540 KB	n = 250, 199047242 is a correct answer
75	Correct	1 ms	8540 KB	n = 250, 61231537449 is a correct answer
76	Correct	1 ms	8540 KB	n = 250, 126000000001 is a correct answer
77	Correct	2 ms	8540 KB	n = 250, 127000000000 is a correct answer
78	Correct	2 ms	8540 KB	n = 250, 2123470094 is a correct answer
79	Correct	1 ms	8628 KB	n = 250, 6545 is a correct answer
80	Correct	1 ms	8540 KB	n = 250, 6731 is a correct answer
81	Correct	1 ms	8536 KB	n = 108, 15322 is a correct answer
82	Correct	1 ms	8536 KB	n = 250, 39952 is a correct answer
83	Correct	1 ms	8540 KB	n = 250, 41156 is a correct answer
84	Correct	1 ms	8540 KB	n = 250, 12881 is a correct answer
85	Correct	1 ms	8540 KB	n = 250, 213812 is a correct answer
86	Correct	1 ms	8540 KB	n = 250, 194188 is a correct answer
87	Correct	1 ms	8540 KB	n = 500, 199300822 is a correct answer
88	Correct	1 ms	8540 KB	n = 500, 127613044387 is a correct answer
89	Correct	1 ms	8540 KB	n = 500, 251000000001 is a correct answer
90	Correct	1 ms	8540 KB	n = 500, 252000000000 is a correct answer
91	Correct	1 ms	8540 KB	n = 500, 199378978 is a correct answer
92	Correct	1 ms	8540 KB	n = 500, 199551149 is a correct answer
93	Correct	1 ms	8540 KB	n = 400, 7177 is a correct answer
94	Correct	1 ms	8540 KB	n = 400, 10067 is a correct answer
95	Correct	1 ms	8536 KB	n = 500, 198631068 is a correct answer
96	Correct	1 ms	8540 KB	n = 400, 10814 is a correct answer
97	Correct	1 ms	8540 KB	n = 400, 9141 is a correct answer
98	Correct	2 ms	8540 KB	n = 500, 5699 is a correct answer
99	Correct	1 ms	8540 KB	n = 500, 13504 is a correct answer
100	Correct	1 ms	8540 KB	n = 500, 31507 is a correct answer
101	Correct	1 ms	8540 KB	n = 500, 199425296 is a correct answer
102	Correct	1 ms	8540 KB	n = 500, 198990259 is a correct answer
103	Correct	1 ms	8536 KB	n = 500, 486155 is a correct answer
104	Correct	1 ms	8536 KB	n = 500, 256468 is a correct answer
105	Correct	1 ms	8540 KB	n = 500, 309873 is a correct answer
106	Correct	1 ms	8540 KB	n = 500, 434764 is a correct answer
107	Correct	3 ms	8540 KB	n = 3000, 2002090624 is a correct answer
108	Correct	2 ms	8540 KB	n = 3000, 2000061654 is a correct answer
109	Correct	2 ms	8540 KB	n = 3000, 2000932313 is a correct answer
110	Correct	2 ms	8540 KB	n = 3000, 2284734775 is a correct answer
111	Correct	2 ms	8540 KB	n = 3000, 2000005545 is a correct answer
112	Correct	2 ms	8536 KB	n = 3000, 2000058220 is a correct answer
113	Correct	2 ms	8700 KB	n = 3000, 2004740516 is a correct answer
114	Correct	3 ms	8796 KB	n = 3000, 909698 is a correct answer
115	Correct	2 ms	8540 KB	n = 3000, 2706266 is a correct answer
116	Correct	2 ms	8540 KB	n = 3000, 2707838 is a correct answer
117	Correct	2 ms	8536 KB	n = 3000, 2829769 is a correct answer
118	Correct	2 ms	8540 KB	n = 3000, 1998685638 is a correct answer
119	Correct	3 ms	8796 KB	n = 3000, 746571 is a correct answer
120	Correct	2 ms	8540 KB	n = 3000, 2744243 is a correct answer
121	Correct	2 ms	8540 KB	n = 3000, 2702210935 is a correct answer
122	Correct	3 ms	8824 KB	n = 3000, 1501000000001 is a correct answer
123	Correct	4 ms	8796 KB	n = 3000, 1502000000000 is a correct answer
124	Correct	2 ms	8540 KB	n = 3000, 2000011887 is a correct answer
125	Correct	2 ms	8540 KB	n = 3000, 2000000012 is a correct answer
126	Correct	2 ms	8540 KB	n = 3000, 2000014932 is a correct answer
127	Correct	2 ms	8796 KB	n = 3000, 2000000010 is a correct answer
128	Correct	2 ms	8540 KB	n = 3000, 93337 is a correct answer
129	Correct	3 ms	8540 KB	n = 3000, 35741 is a correct answer
130	Correct	2 ms	8536 KB	n = 3000, 1999093518 is a correct answer
131	Correct	4 ms	8796 KB	n = 3000, 762334538894 is a correct answer
132	Correct	2 ms	8540 KB	n = 3000, 94081666 is a correct answer
133	Correct	3 ms	8796 KB	n = 3000, 75872047 is a correct answer
134	Correct	3 ms	8796 KB	n = 3000, 3070594 is a correct answer
135	Correct	3 ms	9052 KB	n = 3000, 3003076 is a correct answer
136	Correct	2 ms	8540 KB	n = 3000, 3010050 is a correct answer
137	Correct	2 ms	9048 KB	n = 3000, 1497758 is a correct answer
138	Correct	3 ms	8796 KB	n = 3000, 3025965 is a correct answer
139	Correct	3 ms	8936 KB	n = 3000, 2946044 is a correct answer
140	Correct	2 ms	8540 KB	n = 3000, 2992056 is a correct answer
141	Correct	3 ms	8916 KB	n = 3000, 1490827 is a correct answer
142	Correct	2 ms	8540 KB	n = 3000, 1477754 is a correct answer
143	Correct	2 ms	8540 KB	n = 3000, 2412238 is a correct answer
144	Correct	2 ms	8540 KB	n = 3000, 2742628 is a correct answer
145	Correct	2 ms	8664 KB	n = 3000, 4480584 is a correct answer
146	Correct	2 ms	8792 KB	n = 3000, 4219917 is a correct answer
147	Correct	2 ms	8540 KB	n = 3000, 4207852 is a correct answer
148	Correct	2 ms	8540 KB	n = 3000, 2414542 is a correct answer
149	Correct	2 ms	8540 KB	n = 3000, 1120350 is a correct answer
150	Correct	21 ms	12124 KB	n = 50000, 2000049546 is a correct answer
151	Correct	48 ms	15696 KB	n = 100000, 848578639 is a correct answer
152	Correct	49 ms	19528 KB	n = 100000, 50051 is a correct answer
153	Correct	43 ms	16080 KB	n = 100000, 1999983977 is a correct answer
154	Correct	113 ms	19532 KB	n = 100000, 25012377121147 is a correct answer
155	Correct	110 ms	19372 KB	n = 100000, 24945762330734 is a correct answer
156	Correct	47 ms	15540 KB	n = 100000, 2742000148 is a correct answer
157	Correct	42 ms	15696 KB	n = 100000, 3193426460 is a correct answer
158	Correct	48 ms	15740 KB	n = 100000, 2752140525 is a correct answer
159	Correct	39 ms	15852 KB	n = 100000, 2495802167 is a correct answer
160	Correct	89 ms	19788 KB	n = 100000, 50001000000001 is a correct answer
161	Correct	87 ms	20044 KB	n = 100000, 50002000000000 is a correct answer
162	Correct	39 ms	15588 KB	n = 99999, 2000099997 is a correct answer
163	Correct	39 ms	16976 KB	n = 100000, 2000000559 is a correct answer
164	Correct	33 ms	16340 KB	n = 100000, 2075040000 is a correct answer
165	Correct	38 ms	15708 KB	n = 100000, 2749569701 is a correct answer
166	Correct	39 ms	15800 KB	n = 100000, 2749883772 is a correct answer
167	Correct	37 ms	15832 KB	n = 100000, 1996399503 is a correct answer
168	Correct	45 ms	20304 KB	n = 100000, 945722555 is a correct answer
169	Correct	74 ms	19624 KB	n = 100000, 100172188 is a correct answer
170	Correct	60 ms	26552 KB	n = 100000, 150030536 is a correct answer
171	Correct	33 ms	15184 KB	n = 100000, 100040142 is a correct answer
172	Correct	54 ms	21068 KB	n = 100000, 74983555 is a correct answer
173	Correct	74 ms	20136 KB	n = 100000, 99749623 is a correct answer
174	Correct	76 ms	26684 KB	n = 100000, 150054317 is a correct answer
175	Correct	36 ms	15828 KB	n = 100000, 100165316 is a correct answer
176	Correct	52 ms	17944 KB	n = 100000, 75200683 is a correct answer
177	Correct	36 ms	16280 KB	n = 100000, 677987385 is a correct answer
178	Correct	40 ms	15832 KB	n = 100000, 1892389617 is a correct answer
179	Correct	38 ms	15552 KB	n = 100000, 2023768088 is a correct answer
180	Correct	36 ms	15452 KB	n = 100000, 2064255369 is a correct answer
181	Correct	37 ms	15440 KB	n = 100000, 2071899482 is a correct answer
182	Correct	44 ms	15188 KB	n = 100000, 2006764926 is a correct answer
183	Correct	40 ms	15708 KB	n = 100000, 2010002796 is a correct answer
184	Correct	35 ms	15196 KB	n = 100000, 1985971897 is a correct answer
185	Correct	46 ms	15780 KB	n = 100000, 1991354990 is a correct answer
186	Correct	48 ms	15752 KB	n = 100000, 252662746 is a correct answer
187	Correct	47 ms	15996 KB	n = 100000, 251359741 is a correct answer
188	Correct	46 ms	15864 KB	n = 100000, 252831309 is a correct answer
189	Correct	47 ms	16000 KB	n = 100000, 257146653 is a correct answer
190	Correct	34 ms	16104 KB	n = 100000, 501262012 is a correct answer
191	Correct	78 ms	26176 KB	n = 100000, 83054154 is a correct answer
192	Correct	41 ms	15828 KB	n = 100000, 68547208 is a correct answer
193	Correct	142 ms	28632 KB	n = 300000, 1347279584 is a correct answer
194	Correct	138 ms	43708 KB	n = 300000, 150051 is a correct answer
195	Correct	123 ms	29248 KB	n = 300000, 2000063470 is a correct answer
196	Correct	359 ms	38304 KB	n = 300000, 74955720048028 is a correct answer
197	Correct	361 ms	43708 KB	n = 300000, 75169042952966 is a correct answer
198	Correct	146 ms	28504 KB	n = 300000, 4237488193 is a correct answer
199	Correct	144 ms	28756 KB	n = 300000, 4693165131 is a correct answer
200	Correct	150 ms	28616 KB	n = 300000, 4251307862 is a correct answer
201	Correct	135 ms	28756 KB	n = 300000, 3245649005 is a correct answer
202	Correct	287 ms	43776 KB	n = 300000, 150001000000001 is a correct answer
203	Correct	273 ms	44332 KB	n = 300000, 150002000000000 is a correct answer
204	Correct	86 ms	28144 KB	n = 300000, 2011674404 is a correct answer
205	Correct	84 ms	28148 KB	n = 300000, 2011648876 is a correct answer
206	Correct	158 ms	37308 KB	n = 300000, 2000000008 is a correct answer
207	Correct	146 ms	38284 KB	n = 300000, 2000000003 is a correct answer
208	Correct	116 ms	32068 KB	n = 300000, 2001100086 is a correct answer
209	Correct	120 ms	29500 KB	n = 300000, 112569584 is a correct answer
210	Correct	264 ms	60612 KB	n = 300000, 135548479 is a correct answer
211	Correct	214 ms	45228 KB	n = 300000, 150308864 is a correct answer
212	Correct	290 ms	42384 KB	n = 300000, 300342872 is a correct answer

Subtask #8

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	8540 KB	n = 9, 110 is a correct answer
3	Correct	1 ms	8540 KB	n = 4, 21 is a correct answer
4	Correct	1 ms	8540 KB	n = 3, 4 is a correct answer
5	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
6	Correct	1 ms	8692 KB	n = 2, 3 is a correct answer
7	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
8	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
9	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
10	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
11	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
12	Correct	2 ms	8536 KB	n = 3, 3000000000 is a correct answer
13	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
14	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
15	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
16	Correct	1 ms	8540 KB	n = 5, 4000000000 is a correct answer
17	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
18	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
19	Correct	1 ms	8540 KB	n = 10, 7000000000 is a correct answer
20	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
21	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
22	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
23	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
24	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
25	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
26	Correct	2 ms	8540 KB	n = 10, 206 is a correct answer
27	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
28	Correct	1 ms	8540 KB	n = 4, 2399 is a correct answer
29	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
30	Correct	1 ms	8540 KB	n = 10, 3112 is a correct answer
31	Correct	2 ms	8540 KB	n = 100, 51000000001 is a correct answer
32	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
33	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
34	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
35	Correct	1 ms	8540 KB	n = 100, 52000000000 is a correct answer
36	Correct	1 ms	8540 KB	n = 100, 285 is a correct answer
37	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
38	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
39	Correct	1 ms	8540 KB	n = 2, 62 is a correct answer
40	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
41	Correct	2 ms	8540 KB	n = 3, 29 is a correct answer
42	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
43	Correct	1 ms	8540 KB	n = 2, 3 is a correct answer
44	Correct	1 ms	8540 KB	n = 2, 2000000001 is a correct answer
45	Correct	1 ms	8540 KB	n = 2, 3000000000 is a correct answer
46	Correct	1 ms	8536 KB	n = 3, 3000000000 is a correct answer
47	Correct	1 ms	8540 KB	n = 3, 3000000000 is a correct answer
48	Correct	1 ms	8540 KB	n = 4, 3000000001 is a correct answer
49	Correct	1 ms	8540 KB	n = 4, 4000000000 is a correct answer
50	Correct	1 ms	8628 KB	n = 5, 4000000000 is a correct answer
51	Correct	1 ms	8540 KB	n = 10, 1000000343 is a correct answer
52	Correct	1 ms	8540 KB	n = 10, 3189 is a correct answer
53	Correct	1 ms	8580 KB	n = 10, 7000000000 is a correct answer
54	Correct	1 ms	8540 KB	n = 5, 12 is a correct answer
55	Correct	1 ms	8540 KB	n = 5, 25 is a correct answer
56	Correct	1 ms	8540 KB	n = 2, 122 is a correct answer
57	Correct	1 ms	8540 KB	n = 10, 117 is a correct answer
58	Correct	1 ms	8540 KB	n = 10, 336 is a correct answer
59	Correct	1 ms	8540 KB	n = 10, 438 is a correct answer
60	Correct	1 ms	8540 KB	n = 10, 206 is a correct answer
61	Correct	1 ms	8540 KB	n = 10, 636 is a correct answer
62	Correct	1 ms	8576 KB	n = 4, 2399 is a correct answer
63	Correct	1 ms	8540 KB	n = 10, 10992 is a correct answer
64	Correct	1 ms	8536 KB	n = 10, 3112 is a correct answer
65	Correct	1 ms	8536 KB	n = 100, 51000000001 is a correct answer
66	Correct	1 ms	8540 KB	n = 50, 197881272 is a correct answer
67	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
68	Correct	1 ms	8540 KB	n = 100, 20969 is a correct answer
69	Correct	1 ms	8536 KB	n = 100, 52000000000 is a correct answer
70	Correct	1 ms	8792 KB	n = 100, 285 is a correct answer
71	Correct	1 ms	8540 KB	n = 100, 21272 is a correct answer
72	Correct	1 ms	8540 KB	n = 100, 12161 is a correct answer
73	Correct	1 ms	8540 KB	n = 250, 25037 is a correct answer
74	Correct	1 ms	8540 KB	n = 250, 199047242 is a correct answer
75	Correct	1 ms	8540 KB	n = 250, 61231537449 is a correct answer
76	Correct	1 ms	8540 KB	n = 250, 126000000001 is a correct answer
77	Correct	2 ms	8540 KB	n = 250, 127000000000 is a correct answer
78	Correct	2 ms	8540 KB	n = 250, 2123470094 is a correct answer
79	Correct	1 ms	8628 KB	n = 250, 6545 is a correct answer
80	Correct	1 ms	8540 KB	n = 250, 6731 is a correct answer
81	Correct	1 ms	8536 KB	n = 108, 15322 is a correct answer
82	Correct	1 ms	8536 KB	n = 250, 39952 is a correct answer
83	Correct	1 ms	8540 KB	n = 250, 41156 is a correct answer
84	Correct	1 ms	8540 KB	n = 250, 12881 is a correct answer
85	Correct	1 ms	8540 KB	n = 250, 213812 is a correct answer
86	Correct	1 ms	8540 KB	n = 250, 194188 is a correct answer
87	Correct	1 ms	8540 KB	n = 500, 199300822 is a correct answer
88	Correct	1 ms	8540 KB	n = 500, 127613044387 is a correct answer
89	Correct	1 ms	8540 KB	n = 500, 251000000001 is a correct answer
90	Correct	1 ms	8540 KB	n = 500, 252000000000 is a correct answer
91	Correct	1 ms	8540 KB	n = 500, 199378978 is a correct answer
92	Correct	1 ms	8540 KB	n = 500, 199551149 is a correct answer
93	Correct	1 ms	8540 KB	n = 400, 7177 is a correct answer
94	Correct	1 ms	8540 KB	n = 400, 10067 is a correct answer
95	Correct	1 ms	8536 KB	n = 500, 198631068 is a correct answer
96	Correct	1 ms	8540 KB	n = 400, 10814 is a correct answer
97	Correct	1 ms	8540 KB	n = 400, 9141 is a correct answer
98	Correct	2 ms	8540 KB	n = 500, 5699 is a correct answer
99	Correct	1 ms	8540 KB	n = 500, 13504 is a correct answer
100	Correct	1 ms	8540 KB	n = 500, 31507 is a correct answer
101	Correct	1 ms	8540 KB	n = 500, 199425296 is a correct answer
102	Correct	1 ms	8540 KB	n = 500, 198990259 is a correct answer
103	Correct	1 ms	8536 KB	n = 500, 486155 is a correct answer
104	Correct	1 ms	8536 KB	n = 500, 256468 is a correct answer
105	Correct	1 ms	8540 KB	n = 500, 309873 is a correct answer
106	Correct	1 ms	8540 KB	n = 500, 434764 is a correct answer
107	Correct	3 ms	8540 KB	n = 3000, 2002090624 is a correct answer
108	Correct	2 ms	8540 KB	n = 3000, 2000061654 is a correct answer
109	Correct	2 ms	8540 KB	n = 3000, 2000932313 is a correct answer
110	Correct	2 ms	8540 KB	n = 3000, 2284734775 is a correct answer
111	Correct	2 ms	8540 KB	n = 3000, 2000005545 is a correct answer
112	Correct	2 ms	8536 KB	n = 3000, 2000058220 is a correct answer
113	Correct	2 ms	8700 KB	n = 3000, 2004740516 is a correct answer
114	Correct	3 ms	8796 KB	n = 3000, 909698 is a correct answer
115	Correct	2 ms	8540 KB	n = 3000, 2706266 is a correct answer
116	Correct	2 ms	8540 KB	n = 3000, 2707838 is a correct answer
117	Correct	2 ms	8536 KB	n = 3000, 2829769 is a correct answer
118	Correct	2 ms	8540 KB	n = 3000, 1998685638 is a correct answer
119	Correct	3 ms	8796 KB	n = 3000, 746571 is a correct answer
120	Correct	2 ms	8540 KB	n = 3000, 2744243 is a correct answer
121	Correct	2 ms	8540 KB	n = 3000, 2702210935 is a correct answer
122	Correct	3 ms	8824 KB	n = 3000, 1501000000001 is a correct answer
123	Correct	4 ms	8796 KB	n = 3000, 1502000000000 is a correct answer
124	Correct	2 ms	8540 KB	n = 3000, 2000011887 is a correct answer
125	Correct	2 ms	8540 KB	n = 3000, 2000000012 is a correct answer
126	Correct	2 ms	8540 KB	n = 3000, 2000014932 is a correct answer
127	Correct	2 ms	8796 KB	n = 3000, 2000000010 is a correct answer
128	Correct	2 ms	8540 KB	n = 3000, 93337 is a correct answer
129	Correct	3 ms	8540 KB	n = 3000, 35741 is a correct answer
130	Correct	2 ms	8536 KB	n = 3000, 1999093518 is a correct answer
131	Correct	4 ms	8796 KB	n = 3000, 762334538894 is a correct answer
132	Correct	2 ms	8540 KB	n = 3000, 94081666 is a correct answer
133	Correct	3 ms	8796 KB	n = 3000, 75872047 is a correct answer
134	Correct	3 ms	8796 KB	n = 3000, 3070594 is a correct answer
135	Correct	3 ms	9052 KB	n = 3000, 3003076 is a correct answer
136	Correct	2 ms	8540 KB	n = 3000, 3010050 is a correct answer
137	Correct	2 ms	9048 KB	n = 3000, 1497758 is a correct answer
138	Correct	3 ms	8796 KB	n = 3000, 3025965 is a correct answer
139	Correct	3 ms	8936 KB	n = 3000, 2946044 is a correct answer
140	Correct	2 ms	8540 KB	n = 3000, 2992056 is a correct answer
141	Correct	3 ms	8916 KB	n = 3000, 1490827 is a correct answer
142	Correct	2 ms	8540 KB	n = 3000, 1477754 is a correct answer
143	Correct	2 ms	8540 KB	n = 3000, 2412238 is a correct answer
144	Correct	2 ms	8540 KB	n = 3000, 2742628 is a correct answer
145	Correct	2 ms	8664 KB	n = 3000, 4480584 is a correct answer
146	Correct	2 ms	8792 KB	n = 3000, 4219917 is a correct answer
147	Correct	2 ms	8540 KB	n = 3000, 4207852 is a correct answer
148	Correct	2 ms	8540 KB	n = 3000, 2414542 is a correct answer
149	Correct	2 ms	8540 KB	n = 3000, 1120350 is a correct answer
150	Correct	21 ms	12124 KB	n = 50000, 2000049546 is a correct answer
151	Correct	48 ms	15696 KB	n = 100000, 848578639 is a correct answer
152	Correct	49 ms	19528 KB	n = 100000, 50051 is a correct answer
153	Correct	43 ms	16080 KB	n = 100000, 1999983977 is a correct answer
154	Correct	113 ms	19532 KB	n = 100000, 25012377121147 is a correct answer
155	Correct	110 ms	19372 KB	n = 100000, 24945762330734 is a correct answer
156	Correct	47 ms	15540 KB	n = 100000, 2742000148 is a correct answer
157	Correct	42 ms	15696 KB	n = 100000, 3193426460 is a correct answer
158	Correct	48 ms	15740 KB	n = 100000, 2752140525 is a correct answer
159	Correct	39 ms	15852 KB	n = 100000, 2495802167 is a correct answer
160	Correct	89 ms	19788 KB	n = 100000, 50001000000001 is a correct answer
161	Correct	87 ms	20044 KB	n = 100000, 50002000000000 is a correct answer
162	Correct	39 ms	15588 KB	n = 99999, 2000099997 is a correct answer
163	Correct	39 ms	16976 KB	n = 100000, 2000000559 is a correct answer
164	Correct	33 ms	16340 KB	n = 100000, 2075040000 is a correct answer
165	Correct	38 ms	15708 KB	n = 100000, 2749569701 is a correct answer
166	Correct	39 ms	15800 KB	n = 100000, 2749883772 is a correct answer
167	Correct	37 ms	15832 KB	n = 100000, 1996399503 is a correct answer
168	Correct	45 ms	20304 KB	n = 100000, 945722555 is a correct answer
169	Correct	74 ms	19624 KB	n = 100000, 100172188 is a correct answer
170	Correct	60 ms	26552 KB	n = 100000, 150030536 is a correct answer
171	Correct	33 ms	15184 KB	n = 100000, 100040142 is a correct answer
172	Correct	54 ms	21068 KB	n = 100000, 74983555 is a correct answer
173	Correct	74 ms	20136 KB	n = 100000, 99749623 is a correct answer
174	Correct	76 ms	26684 KB	n = 100000, 150054317 is a correct answer
175	Correct	36 ms	15828 KB	n = 100000, 100165316 is a correct answer
176	Correct	52 ms	17944 KB	n = 100000, 75200683 is a correct answer
177	Correct	36 ms	16280 KB	n = 100000, 677987385 is a correct answer
178	Correct	40 ms	15832 KB	n = 100000, 1892389617 is a correct answer
179	Correct	38 ms	15552 KB	n = 100000, 2023768088 is a correct answer
180	Correct	36 ms	15452 KB	n = 100000, 2064255369 is a correct answer
181	Correct	37 ms	15440 KB	n = 100000, 2071899482 is a correct answer
182	Correct	44 ms	15188 KB	n = 100000, 2006764926 is a correct answer
183	Correct	40 ms	15708 KB	n = 100000, 2010002796 is a correct answer
184	Correct	35 ms	15196 KB	n = 100000, 1985971897 is a correct answer
185	Correct	46 ms	15780 KB	n = 100000, 1991354990 is a correct answer
186	Correct	48 ms	15752 KB	n = 100000, 252662746 is a correct answer
187	Correct	47 ms	15996 KB	n = 100000, 251359741 is a correct answer
188	Correct	46 ms	15864 KB	n = 100000, 252831309 is a correct answer
189	Correct	47 ms	16000 KB	n = 100000, 257146653 is a correct answer
190	Correct	34 ms	16104 KB	n = 100000, 501262012 is a correct answer
191	Correct	78 ms	26176 KB	n = 100000, 83054154 is a correct answer
192	Correct	41 ms	15828 KB	n = 100000, 68547208 is a correct answer
193	Correct	142 ms	28632 KB	n = 300000, 1347279584 is a correct answer
194	Correct	138 ms	43708 KB	n = 300000, 150051 is a correct answer
195	Correct	123 ms	29248 KB	n = 300000, 2000063470 is a correct answer
196	Correct	359 ms	38304 KB	n = 300000, 74955720048028 is a correct answer
197	Correct	361 ms	43708 KB	n = 300000, 75169042952966 is a correct answer
198	Correct	146 ms	28504 KB	n = 300000, 4237488193 is a correct answer
199	Correct	144 ms	28756 KB	n = 300000, 4693165131 is a correct answer
200	Correct	150 ms	28616 KB	n = 300000, 4251307862 is a correct answer
201	Correct	135 ms	28756 KB	n = 300000, 3245649005 is a correct answer
202	Correct	287 ms	43776 KB	n = 300000, 150001000000001 is a correct answer
203	Correct	273 ms	44332 KB	n = 300000, 150002000000000 is a correct answer
204	Correct	86 ms	28144 KB	n = 300000, 2011674404 is a correct answer
205	Correct	84 ms	28148 KB	n = 300000, 2011648876 is a correct answer
206	Correct	158 ms	37308 KB	n = 300000, 2000000008 is a correct answer
207	Correct	146 ms	38284 KB	n = 300000, 2000000003 is a correct answer
208	Correct	116 ms	32068 KB	n = 300000, 2001100086 is a correct answer
209	Correct	120 ms	29500 KB	n = 300000, 112569584 is a correct answer
210	Correct	264 ms	60612 KB	n = 300000, 135548479 is a correct answer
211	Correct	214 ms	45228 KB	n = 300000, 150308864 is a correct answer
212	Correct	290 ms	42384 KB	n = 300000, 300342872 is a correct answer
213	Correct	978 ms	98984 KB	n = 1000000, 500001000000001 is a correct answer
214	Correct	934 ms	98716 KB	n = 1000000, 500002000000000 is a correct answer
215	Correct	558 ms	59952 KB	n = 1000000, 849747675 is a correct answer
216	Correct	453 ms	106124 KB	n = 1000000, 500000 is a correct answer
217	Correct	426 ms	59956 KB	n = 1000000, 2000441267 is a correct answer
218	Correct	1280 ms	93636 KB	n = 1000000, 250246841268133 is a correct answer
219	Correct	1141 ms	98668 KB	n = 1000000, 250261950040679 is a correct answer
220	Correct	573 ms	60032 KB	n = 1000000, 2748631751 is a correct answer
221	Correct	640 ms	58668 KB	n = 1000000, 9947951774 is a correct answer
222	Correct	661 ms	58532 KB	n = 1000000, 9990368145 is a correct answer
223	Correct	657 ms	58848 KB	n = 1000000, 9497779480 is a correct answer
224	Correct	402 ms	60724 KB	n = 1000000, 2498635413 is a correct answer
225	Correct	413 ms	73364 KB	n = 1000000, 1896584891 is a correct answer
226	Correct	394 ms	89432 KB	n = 1000000, 968194076 is a correct answer
227	Correct	339 ms	57792 KB	n = 1000000, 1998881127 is a correct answer
228	Correct	354 ms	57536 KB	n = 1000000, 2500842518 is a correct answer
229	Correct	346 ms	57284 KB	n = 1000000, 2500492323 is a correct answer
230	Correct	563 ms	90496 KB	n = 1000000, 2000000999 is a correct answer
231	Correct	366 ms	61120 KB	n = 1000000, 991856281 is a correct answer
232	Correct	1052 ms	186248 KB	n = 1000000, 532264598 is a correct answer
233	Correct	710 ms	118240 KB	n = 1000000, 500379848 is a correct answer
234	Correct	1071 ms	103824 KB	n = 1000000, 1000857674 is a correct answer