## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Keep a counter and set it to 0
Assume you have a string or char array of secret password

If it matches with first digit secret[count] of the password increase counter by 1
If it does not match, resent counter to 0

At any point say counter = k, if input number does not match with secret[k] of the password then resent count to 0; back to square one

Comment hidden because of low score. Click to expand.
0

b=passcode;
pressKey:
start;
store a=0;
loop1:
input num;
a = (a*10) + num;
while a.length != b.length goto loop1;
store c = checkNum(num);
if k is true
print "Succeed";
reset a;
else
goto loop1;

checkNum(num):
val = Math.power(10,b.length);
num = num % val;
if num == b
return true;
else
return false;

Comment hidden because of low score. Click to expand.
0

Can't we apply KMP and find the password substring in the input.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````static String getKeys(int length){
ArrayList<Object> multiArray = new ArrayList<>();
multiArray = initArray(length , multiArray);

StringBuffer keys = new StringBuffer();
ArrayList<Integer> lastNum =  new ArrayList<>();

for(int i =1; i < length; i++){
keys.append("0");
}

while(nextKey(keys, lastNum, multiArray, 1, length)){}

System.out.println(keys.length());

return keys.toString();
}

static Boolean nextKey(StringBuffer keys, ArrayList<Integer> lastNum, ArrayList<Object> multiArray, int index, int length){

//System.out.println(index + "    "+length);

if(index == length){
for(int i=9; i>=0; i--){
if((Boolean)multiArray.get(i) == true){
multiArray.remove(i);
lastNum.remove(0);
keys.append(i);
//System.out.println(i);
return true;
}
}
return false;
}
else{
//int nextIndex = index + 1;
return nextKey(keys,lastNum,(ArrayList<Object>) multiArray.get(lastNum.get(index-1)),index+1,length);
}

}
static ArrayList<Object> initArray(int length,ArrayList<Object> pList){
if(length == 1){
for(int i=0;i<10;i++){
}
}
else if(length > 1){
for (int i=0;i<10;i++){
ArrayList<Object> temp = new ArrayList<>();
}
}
return pList;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi could you clarify these both statements in the problem .
1. First it says, keycode panel does not reset when incorrect sequence is entered.
2. Next in the below lines it says, panel does not reset after every sequence.

when does the sequence actually does not reset ? and also when correct code is sequence of 5 digits, are we allowed to enter more than 5 digits at a time ???

Comment hidden because of low score. Click to expand.
1
of 1 vote

I've tried to reword the question a bit to be clearer.

The sequence will never reset. Perhaps a better way to think of this is you are feeding a long stream of keypresses to the keypad where the keypad always remembers the last 4 digits entered (in the order they were entered). Every time you press another key, the keypad looks at the last 4 digits entered and sees if these 4 digits plus your current keypress yield the correct sequence. If so, the API returns true, else false.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi could you clarify these both statements in the problem .
1. First it says, keycode panel does not reset when incorrect sequence is entered.
2. Next in the below lines it says, panel does not reset after every sequence.

when does the sequence actually does not reset ? and also when correct code is sequence of 5 digits, are we allowed to enter more than 5 digits at a time ???

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a queue:
Algorithm:
Fill queue with first n elements of actual pattern
For every new element, push number to the end of the queue and pop first element.
If no more elements to push, do the Panel.key(Node *n) check to see if pattern matches elements in the queue.
Space complexity O(n) for queue

Comment hidden because of low score. Click to expand.
0

This solves a portion of the problem where you need to track the sequence of keys being tested so you can return it (the code) if it's correct. However, what is the sequence of keypresses you will enter to eventually find the correct code in an efficient manner in terms of the number of keypresses?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about the tail-recursive way to try all possible combinations?
The time complexity would be O(n^2).

``````int findGenericKey(char *entered)
{
if (!entered)
return -1;  // -1 means "failed to find the key"

int key = 0 ;
int i ;
int len = strlen(entered);
&& i < len)
{
i++;
key = key * 10 + entered[i] - '0';
if (key < 0)
{
// assume the key be positive
// when it gets to negative, the value has been overflown
// no need to try more in this loop
break;  // out of the while-loop
}
} // end of while

if (    key >= 0  // again assume the key is non-negative
return key ;  // found the key
else
return findKey(entered + 1);
}``````

Comment hidden because of low score. Click to expand.
0

Oops, typo:

``````i++;
key = key * 10 + entered[i] - '0';``````

should be:

``key = key * 10 + entered[i++] - '0';``

and the last line

``return findKey(entered + 1);``

should be:

``return findGenericKey(entered + 1);``

Comment hidden because of low score. Click to expand.
0

If you post code, only use actual working code that you tested.

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a mean question to ask.

i think the approach is to give a stream of numbers such that every 5 consecutive numbers gives you a unique number. I don't know how to do this though.

There is another option which is to keep a hashtable of all numbers from 0 to 10000, then when you add another number to the stream, you check which digit you can add and see if this new digit with the last 4 numbers in stream are already in the hashtable? This ends up being more cumbersome than brute force though...

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. implemented with queue which can hold upto 5 elements -
2. read key press , push value into the queue .
3. if size of queue is five then check combination(if true return queue else goto 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This solves both (1) and the generic case (2).

1. Set the length starting at 0. It will keep increasing later
2. Try digits and see what combination of size "length" was just typed. If it's a new combination, add it in a hashtable "comboHash". If it's not, cancel that last digit and try a new one.
3. If we run out of combinations of size "length", increment length
4. Check in the digits history to see what new combinations of size "length" have already been tried, and fill up our "comboHash".
5. Go back to step 2.

``````function output(obj) {
console.log(obj);
document.body.innerHTML += obj + "<br>";
}

function checkDigitsForSolution(solution) {
return function(digits) {
if(digits.slice(digits.length-solution.length).join("")==solution) {
output("Found combination:"+solution);
return true;
}
else {
return false;
}
}
}

function solveCombinations(checkDigits) {

var comboHash = {};
var highestReachedLength = 0;
var digits = [];
var comboCount = 0;

do {
var newDigit = -1;
for(var length=highestReachedLength;length<=digits.length;length++) {

if(length>highestReachedLength) {
// fillup comboHash
for(var c in comboHash) {
var index = comboHash[c];
var combo = digits.slice(index,index+length+1).join("");
if(comboHash[combo]===undefined) {
comboHash[combo] = index;
comboCount++;
}
}
highestReachedLength = length;
}
var lastCombinationArray = digits.slice(digits.length-length);
for(var d=0;d<=9;d++) {
lastCombinationArray.push(d);
var combination = lastCombinationArray.join("");
if(comboHash[combination]===undefined) {
comboHash[combination] = (digits.length-length);
newDigit = d;
comboCount++;
break;
}
lastCombinationArray.pop();
}
if(newDigit>=0) {
break;
}
}

digits.push(newDigit);
} while(!checkDigits(digits));

output((digits.length>100?"...":"")+ digits.join("").slice(digits.length-100));
output("Digits typed: "+digits.length);
output("Combinations tested: "+comboCount);
}

solveCombinations(checkDigitsForSolution("102"));
output("============");
solveCombinations(checkDigitsForSolution("911"));
output("============");
solveCombinations(checkDigitsForSolution("1978"));``````

Output:

``````Found combination:102
0123456789002030405060708091000101102
Digits typed: 37
Combinations tested: 73
============
Found combination:911
...4031403240255003540403340265004540514041405240424053403550127003630364036502150225013600281009000911
Digits typed: 1046
Combinations tested: 1284
============
Found combination:1978
...8784108785007786106786205787104787202878101378101478101578003278001578101678001678101778000988001978
Digits typed: 207036
Combinations tested: 228608``````

Comment hidden because of low score. Click to expand.
0

I had this idea too, but i'm not sure if it's better than brute force- mainly because for every combination you try, you have to see if adding digit 0,1,2,3,4,5,6,7,8,9 are in the hashtable. This means, you will (at worst case) test 10 digits each time, and do this 100,000 times, which is worse than brute force of 500,000 checks

Comment hidden because of low score. Click to expand.
0

I think that for this problem, the goal is to press the least number of keys, rather than find the combination more efficiently.

Comment hidden because of low score. Click to expand.
0

I tried it with linked list , please have a look and improve me :)

``````public class LinkedList {
int data;

{
this.data=0;
this.next=null;

}
{
this.data=data;
this.next=null;
}

{
if(root==null)
{
root.data=data;
return root;
}
else
{

newnode.data=data;
newnode.next=root;

return newnode;
}

}

{
if(root==null)
return;
else
{
while(root.next!=null)
{
prev=root;
root=root.next;
}
prev.next=null;
}
}

{
if(root==null)
{return ;}
else
{
while(root!=null)
{
System.out.println(root.data);
root=root.next;
}
}
}

}

*************************************************

import java.util.Scanner;

public class SolutionClass {
public static void main(String args[])
{
int arr[]={1,0,2};

boolean flag=false;
Scanner sc=new Scanner(System.in);
String seq=sc.next();
int len=seq.length();
int count=0;
int data=0,j=1;

while(count!=(len-1))
{
count++;
data=Integer.parseInt(seq.charAt(j)+"");
j++;
if(count>=(arr.length-1))
{
flag=CheckSequence(root,arr);
if(flag==true)
break;

}

}

if(flag==true)
{
System.out.println("Acess Granted");
}
else
{
}

}

private static boolean CheckSequence(LinkedList root2, int[] arr) {
// TODO Auto-generated method stub

for(int i=(arr.length-1);i>=0;i--)
{
if(!(arr[i]==root2.data))
{
return false;

}
root2=root2.next;
}

return true;
}

}``````

Comment hidden because of low score. Click to expand.
0

import java.util.Scanner;

private int length = 0;
node temp= null;
private class node{
private int data;
private node next;

public node(int d){
this.data = d;
this.next = null;
}
}

{
node nd = new node(d);
{

}
else
{
}
length++;
}
private void delete(){

node prev = null;
while(cur.next!= null)
{
prev = cur;
cur= cur.next;
}
prev.next = null;
length--;

}

private int listSize()
{
return length;
}

private StringBuilder stringBuild()
{

StringBuilder str = new StringBuilder();
while(temp != null)
{
str.append(String.valueOf(temp.data));
temp = temp.next;
}
return str;

}

public static void main(String[] args)
{
System.out.println("Enter keys");

int key;
Scanner sc = new Scanner(System.in);
while((key = sc.nextInt())!= -1)
{

if(ps.listSize() == 5)
{

// Check if the keys are correct
// Build the string
{
System.out.println("Unlocked");
System.exit(0);
}
ps.delete();

}

}
}

}

Comment hidden because of low score. Click to expand.
0

``````import java.util.Scanner;

private int length = 0;
node temp= null;
private class node{
private int data;
private node next;

public node(int d){
this.data = d;
this.next = null;
}
}

{
node nd = new node(d);
{

}
else
{
}
length++;
}
private void delete(){

node prev = null;
while(cur.next!= null)
{
prev = cur;
cur= cur.next;
}
prev.next = null;
length--;

}

private int listSize()
{
return length;
}

private StringBuilder stringBuild()
{

StringBuilder str = new StringBuilder();
while(temp != null)
{
str.append(String.valueOf(temp.data));
temp = temp.next;
}
return str;

}

public static void main(String[] args)
{
System.out.println("Enter keys");

int key;
Scanner sc = new Scanner(System.in);
while((key = sc.nextInt())!= -1)
{

if(ps.listSize() == 5)
{

// Check if the keys are correct
// Build the string
{
System.out.println("Unlocked");
System.exit(0);
}
ps.delete();

}

}
}

}``````

Comment hidden because of low score. Click to expand.
0

``````import java.util.Scanner;

private int length = 0;
node temp= null;
private class node{
private int data;
private node next;

public node(int d){
this.data = d;
this.next = null;
}
}

{
node nd = new node(d);
{

}
else
{
}
length++;
}
private void delete(){

node prev = null;
while(cur.next!= null)
{
prev = cur;
cur= cur.next;
}
prev.next = null;
length--;

}

private int listSize()
{
return length;
}

private StringBuilder stringBuild()
{

StringBuilder str = new StringBuilder();
while(temp != null)
{
str.append(String.valueOf(temp.data));
temp = temp.next;
}
return str;

}

public static void main(String[] args)
{
System.out.println("Enter keys");

int key;
Scanner sc = new Scanner(System.in);
while((key = sc.nextInt())!= -1)
{

if(ps.listSize() == 5)
{

// Check if the keys are correct
// Build the string
{
System.out.println("Unlocked");
System.exit(0);
}
ps.delete();

}

}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool KeyPadPressKey(int entry)
{
#define LENGTH_KEY	(5)
static char code[LENGTH_KEY+1] = {"12345"};

static int nStep = 0;

if( nStep < LENGTH_KEY ){//array access violation check
if( entry==code[nStep] ){
nStep++;	//serial sequence correct case
}
else{
nStep = 0;	//wrong key. from the start again.
}
}

//code check
if( nStep >= LENGTH_KEY ){	//correct code in a row
nStep = 0;	//init
return true;
}
//else
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````inputString = ['00000']
for i in range(1, 10):
inputString.append("0000" + str(i))
for i in range(10, 100):
inputString.append("000" + str(i))
for i in range(100, 1000):
inputString.append("00" + str(i))
for i in range(1000, 10000):
inputString.append("0" + str(i))
for i in range(10000, 100000):
inputString = inputString + str(i)
inputString = ''.join(inputString)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````inputString = ['00000']
for i in range(1, 10):
inputString.append("0000" + str(i))
for i in range(10, 100):
inputString.append("000" + str(i))
for i in range(100, 1000):
inputString.append("00" + str(i))
for i in range(1000, 10000):
inputString.append("0" + str(i))
for i in range(10000, 100000):
inputString = inputString + str(i)
inputString = ''.join(inputString)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RandomPuzzles
{
class LockerKey
{
private static string key = "98345";
private static string sequence;
private static int numKeysEntered;
private static Dictionary<string, bool> elapsedSet = new Dictionary<string, bool>();

public static string Solve()
{
sequence = "00000";
{
for (int i = 1; i <= 4; i++)
{
var newKeys = GetKeyOfLength(i, 5);
if (newKeys != null)
{
var isMatchFound = EnterKeys(newKeys);

if (isMatchFound)
{
var start = sequence.Length - 5;
var finalKey = sequence.Substring(start, 5);
return finalKey;
}
break;
}
}
}
return null;
}

private static bool IsKey()
{
var start = sequence.Length - 5;
var newKey = sequence.Substring(start, 5);
if (newKey == key)
{
return true;
}
return false;
}

private static bool EnterKeys(string newKeys)
{
foreach (char c in newKeys.ToCharArray())
{
sequence += c.ToString();
numKeysEntered++;
}

var rtnValue = IsKey();
return rtnValue;
}

private static string GetKeyOfLength(int length, int maxLength)
{
Console.WriteLine("GetKeyOfLength called with {0} and {1}", length, maxLength);
string appendedString = null;
var maxValue = Math.Pow(10, length);
var reuseLength = maxLength - length;
var reuseStart = sequence.Length - reuseLength;
var reuseString = sequence.Substring (reuseStart, reuseLength);
for (int i = 0; i < maxValue; i++)
{
var newKey = reuseString + appendedString;
if (!elapsedSet.Keys.Contains(newKey))
{
Console.WriteLine("AppendedString: {0} New Key: {1} i: {2} maxValue: {3}", appendedString, newKey, i, maxValue);
break;
}
else
{
appendedString = null;
}
}
return appendedString;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe I understood the task not fully correct, but as for me the goal was to build a search of secret combination of n digits such way that we use minimum of key presses. My solution uses a bitset to keep which sequence of numbers we already visited and which not. Actually we just go through all int values from 0 to 10^n and check whether we have already visit the current number or not. If we add a new n-digits to the sequence we concatenate it with previous n digits and visit all sub-strings.

``````import java.util.BitSet;

/**
* Created by sis on 5/31/15.
*/
public class CareerCup_5126565916573696 {
public static void main(String[] args) {
new Problem(5).naive();
}

static class Problem {
private int length;
private final BitSet visited;
private String previousString;

private int totalKeys;
private int duplications;
private int maxValue;

Problem(int length) {
this.length = length;
this.maxValue = (int) Math.pow(10.0, length);
this.visited = new BitSet(maxValue);
}

private void innerCheck(String currentString) {
if (previousString != null) {
String concat = previousString + currentString;
for (int i = 1; i < concat.length() - length; i++) {
checkAndVisit(concat.substring(i, i + length));
}
}

checkAndVisit(currentString);
previousString = currentString;
}

private void checkAndVisit(String str) {
int value = Integer.valueOf(str);
if (visited.get(value)) {
//                uncomment this line to see duplicated values
//                System.out.printf("!!!! duplication: %05d %n", value);
duplications++;
} else {
visited.set(value, true);
}
}

public void naive() {
final String fmt = "%0" + length + "d";

for (int i = 0; i < maxValue; i++) {
if (!visited.get(i)) {

String str = String.format(fmt, i);
innerCheck(str);

totalKeys += length;
}
}

System.out.printf("Total duplications: %d%n", duplications);
System.out.printf("Total keys: %d%n", totalKeys);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I was thinking to use trie. Get all 5 dizits number in a trie. For this even the trie generation code will be simpler as we start ( 0......9) and each will have children (0......9) till 5 level. Now start with "0000" and we have a choice at (0....9) at first. Take the 0. delete the node 0 and go to its parent. As the number ending with this is reached.
Repeat the process till the trie has an element. TC ( num 0f digits) ^ ( length).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the algorithm to solve this problem:
1. Store the n digit sequence in string. Say it is a 3 digit and stored as string Pwd = "123";
2. Store the input sequence. Say string seq = "451234"
3. Define variable to store the Pwd length, int pwdlen = Pwd.lenght; = 3
4. Define variable to store the seq lenght, int seqlen = seq.length; = 6
5. define two variables int i = o and int k = 0;

Execute for loop for i = 0 to i< seqlen; i++
if(pwd[k]==seq[i])
increment k by 1
if (k==pwdlen) return true
else k = 0
At the end return false;

Code snippet below:

``````public bool FindMatch()
{

Console.WriteLine("Enter Sequence");
int i = 0;
int k = 0;
int pwdlength = pwd.Length;
int seqlength = inputSequence.Length;

for (i = 0; i < seqlength; i++)
{
if (pwd[k] == inputSequence[i])
{
k++;
if (k != 0 && k == pwdlength) return true;
}
else k = 0;
Console.WriteLine(i);

}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public bool FindMatch()
{
Console.WriteLine("Enter Sequence");

int i = 0;
int k = 0;
int pwdlength = pwd.Length;
int seqlength = inputSequence.Length;

for (i = 0; i < seqlength; i++)
{
if (pwd[k] == inputSequence[i])
{
k++;
if (k != 0 && k == pwdlength) return true;
}
else k = 0;
Console.WriteLine(i);

}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use kmp string matching algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is called a "DeBruijn" sequence. The theory behind finding it is quite complicated, and so is the algorithm to create it. I suppose the intent of this question in an interview is to look for a good approximation, rather than the reall full algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I tried this and it worked

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

string keyPressed(int num){
stringstream ss;
string key = "12345";
string test;
ss << num;
string str;
ss >> str;
for (int i = 0; i <= str.length() - key.length(); i++){
test = str.substr(i, key.length());
if (test == key){
return "worked";
}
}
return "failed";
}
int main(){
cout << "The keypad unlocking " << keyPressed(6712345) << endl;
getchar();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I tried this code and it worked for me

``````#include <iostream>
#include <string>
#include <sstream>
using namespace std;

string keyPressed(int num){
stringstream ss;
string key = "12345";
string test;
ss << num;
string str;
ss >> str;
for (int i = 0; i <= str.length() - key.length(); i++){
test = str.substr(i, key.length());
if (test == key){
return "worked";
}
}
return "failed";
}
int main(){
cout << "The keypad unlocking " << keyPressed(6712345) << endl;
getchar();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about a modified KMP algorithm???
the password is the substring that you want to search from the sequence of the key presses which maybe treated as a longer string

Comment hidden because of low score. Click to expand.
0
of 0 vote

00009999989999799996999959999499993999929999199990999889998799986999859998499983999829998199980999789997799976999759997499973999729997199970999689996799966999659996499963999629996199960999589995799956999559995499953999529995199950999489994799946999459994499943999429994199940999389993799936999359993499933999329993199930999289992799926999259992499923999229992199920999189991799916999159991499913999129991199910999089990799906999059990499903999029990199900998989989799896998959989499893998929989199890998889988799886998859988499883998829988199880998789987799876998759987499873998729987199870998689986799866998659986499863998629986199860998589985799856998559985499853998529985199850998489984799846998459984499843998429984199840998389983799836998359983499833998329983199830998289982799826998259982499823998229982199820998189981799816998159981499813998129981199810998089980799806998059980499803998029980199800997989979799796997959979499793997929979199790997889978799786997859978499783997829978199780997789977799776997759977499773997729977199770997689976799766997659976499763997629976199760997589975799756997559975499753997529975199750997489974799746997459974499743997429974199740997389973799736997359973499733997329973199730997289972799726997259972499723997229972199720997189971799716997159971499713997129971199710997089970799706997059970499703997029970199700996989969799696996959969499693996929969199690996889968799686996859968499683996829968199680996789967799676996759967499673996729967199670996689966799666996659966499663996629966199660996589965799656996559965499653996529965199650996489964799646996459964499643996429964199640996389963799636996359963499633996329963199630996289962799626996259962499623996229962199620996189961799616996159961499613996129961199610996089960799606996059960499603996029960199600995989959799596995959959499593995929959199590995889958799586995859958499583995829958199580995789957799576995759957499573995729957199570995689956799566995659956499563995629956199560995589955799556995559955499553995529955199550995489954799546995459954499543995429954199540995389953799536995359953499533995329953199530995289952799526995259952499523995229952199520995189951799516995159951499513995129951199510995089950799506995059950499503995029950199500994989949799496994959949499493994929949199490994889948799486994859948499483994829948199480994789947799476994759947499473994729947199470994689946799466994659946499463994629946199460994589945799456994559945499453994529945199450994489944799446994459944499443994429944199440994389943799436994359943499433994329943199430994289942799426994259942499423994229942199420994189941799416994159941499413994129941199410994089940799406994059940499403994029940199400993989939799396993959939499393993929939199390993889938799386993859938499383993829938199380993789937799376993759937499373993729937199370993689936799366993659936499363993629936199360993589935799356993559935499353993529935199350993489934799346993459934499343993429934199340993389933799336993359933499333993329933199330993289932799326993259932499323993229932199320993189931799316993159931499313993129931199310993089930799306993059930499303993029930199300992989929799296992959929499293992929929199290992889928799286992859928499283992829928199280992789927799276992759927499273992729927199270992689926799266992659926499263992629926199260992589925799256992559925499253992529925199250992489924799246992459924499243992429924199240992389923799236992359923499233992329923199230992289922799226992259922499223992229922199220992189921799216992159921499213992129921199210992089920799206992059920499203992029920199200991989919799196991959919499193991929919199190991889918799186991859918499183991829918199180991789917799176991759917499173991729917199170991689916799166991659916499163991629916199160991589915799156991559915499153991529915199150991489914799146991459914499143991429914199140991389913799136991359913499133991329913199130991289912799126991259912499123991229912199120991189911799116991159911499113991129911199110991089910799106991059910499103991029910199100990989909799096990959909499093990929909199090990889908799086990859908499083990829908199080990789907799076990759907499073990729907199070990689906799066990659906499063990629906199060990589905799056990559905499053990529905199050990489904799046990459904499043990429904199040990389903799036990359903499033990329903199030990289902799026990259902499023990229902199020990189901799016990159901499013990129901199010990089900799006990059900499003990029900199000989889898798986989859898498983989829898198980989789897798976989759897498973989729897198970989689896798966989659896498963989629896198960989589895798956989559895498953989529895198950989489894798946989459894498943989429894198940989389893798936989359893498933989329893198930989289892798926989259892498923989229892198920989189891798916989159891498913989129891198910989089890798906989059890498903989029890198900988979889698895988949889398892988919889098888988879888698885988849888398882988819888098878988779887698875988749887398872988719887098868988679886698865988649886398862988619886098858988579885698855988549885398852988519885098848988479884698845988449884398842988419884098838988379883698835988349883398832988319883098828988279882698825988249882398822988219882098818988179881698815988149881398812988119881098808988079880698805988049880398802988019880098797987969879598794987939879298791987909878898787987869878598784987839878298781987809877898777987769877598774987739877298771987709876898767987669876598764987639876298761987609875898757987569875598754987539875298751987509874898747987469874598744987439874298741987409873898737987369873598734987339873298731987309872898727987269872598724987239872298721987209871898717987169871598714987139871298711987109870898707987069870598704987039870298701987009869798696986959869498693986929869198690986889868798686986859868498683986829868198680986789867798676986759867498673986729867198670986689866798666986659866498663986629866198660986589865798656986559865498653986529865198650986489864798646986459864498643986429864198640986389863798636986359863498633986329863198630986289862798626986259862498623986229862198620986189861798616986159861498613986129861198610986089860798606986059860498603986029860198600985979859698595985949859398592985919859098588985879858698585985849858398582985819858098578985779857698575985749857398572985719857098568985679856698565985649856398562985619856098558985579855698555985549855398552985519855098548985479854698545985449854398542985419854098538985379853698535985349853398532985319853098528985279852698525985249852398522985219852098518985179851698515985149851398512985119851098508985079850698505985049850398502985019850098497984969849598494984939849298491984909848898487984869848598484984839848298481984809847898477984769847598474984739847298471984709846898467984669846598464984639846298461984609845898457984569845598454984539845298451984509844898447984469844598444984439844298441984409843898437984369843598434984339843298431984309842898427984269842598424984239842298421984209841898417984169841598414984139841298411984109840898407984069840598404984039840298401984009839798396983959839498393983929839198390983889838798386983859838498383983829838198380983789837798376983759837498373983729837198370983689836798366983659836498363983629836198360983589835798356983559835498353983529835198350983489834798346983459834498343983429834198340983389833798336983359833498333983329833198330983289832798326983259832498323983229832198320983189831798316983159831498313983129831198310983089830798306983059830498303983029830198300982979829698295982949829398292982919829098288982879828698285982849828398282982819828098278982779827698275982749827398272982719827098268982679826698265982649826398262982619826098258982579825698255982549825398252982519825098248982479824698245982449824398242982419824098238982379823698235982349823398232982319823098228982279822698225982249822398222982219822098218982179821698215982149821398212982119821098208982079820698205982049820398202982019820098197981969819598194981939819298191981909818898187981869818598184981839818298181981809817898177981769817598174981739817298171981709816898167981669816598164981639816298161981609815898157981569815598154981539815298151981509814898147981469814598144981439814298141981409813898137981369813598134981339813298131981309812898127981269812598124981239812298121981209811898117981169811598114981139811298111981109810898107981069810598104981039810298101981009809798096980959809498093980929809198090980889808798086980859808498083980829808198080980789807798076980759807498073980729807198070980689806798066980659806498063980629806198060980589805798056980559805498053980529805198050980489804798046980459804498043980429804198040980389803798036980359803498033980329803198030980289802798026980259802498023980229802198020980189801798016980159801498013980129801198010980089800798006980059800498003980029800198000979789797797976979759797497973979729797197970979689796797966979659796497963979629796197960979589795797956979559795497953979529795197950979489794797946979459794497943979429794197940979389793797936979359793497933979329793197930979289792797926979259792497923979229792197920979189791797916979159791497913979129791197910979089790797906979059790497903979029790197900978969789597894978939789297891978909788897887978869788597884978839788297881978809787897877978769787597874978739787297871978709786897867978669786597864978639786297861978609785897857978569785597854978539785297851978509784897847978469784597844978439784297841978409783897837978369783597834978339783297831978309782897827978269782597824978239782297821978209781897817978169781597814978139781297811978109780897807978069780597804978039780297801978009779697795977949779397792977919779097788977879778697785977849778397782977819778097778977779777697775977749777397772977719777097768977679776697765977649776397762977619776097758977579775697755977549775397752977519775097748977479774697745977449774397742977419774097738977379773697735977349773397732977319773097728977279772697725977249772397722977219772097718977179771697715977149771397712977119771097708977079770697705977049770397702977019770097696976959769497693976929769197690976889768797686976859768497683976829768197680976789767797676976759767497673976729767197670976689766797666976659766497663976629766197660976589765797656976559765497653976529765197650976489764797646976459764497643976429764197640976389763797636976359763497633976329763197630976289762797626976259762497623976229762197620976189761797616976159761497613976129761197610976089760797606976059760497603976029760197600975969759597594975939759297591975909758897587975869758597584975839758297581975809757897577975769757597574975739757297571975709756897567975669756597564975639756297561975609755897557975569755597554975539755297551975509754897547975469754597544975439754297541975409753897537975369753597534975339753297531975309752897527975269752597524975239752297521975209751897517975169751597514975139751297511975109750897507975069750597504975039750297501975009749697495974949749397492974919749097488974879748697485974849748397482974819748097478974779747697475974749747397472974719747097468974679746697465974649746397462974619746097458974579745697455974549745397452974519745097448974479744697445974449744397442974419744097438974379743697435974349743397432974319743097428974279742697425974249742397422974219742097418974179741697415974149741397412974119741097408974079740697405974049740397402974019740097396973959739497393973929739197390973889738797386973859738497383973829738197380973789737797376973759737497373973729737197370973689736797366973659736497363973629736197360973589735797356973559735497353973529735197350973489734797346973459734497343973429734197340973389733797336973359733497333973329733197330973289732797326973259732497323973229732197320973189731797316973159731497313973129731197310973089730797306973059730497303973029730197300972969729597294972939729297291972909728897287972869728597284972839728297281972809727897277972769727597274972739727297271972709726897267972669726597264972639726297261972609725897257972569725597254972539725297251972509724897247972469724597244972439724297241972409723897237972369723597234972339723297231972309722897227972269722597224972239722297221972209721897217972169721597214972139721297211972109720897207972069720597204972039720297201972009719697195971949719397192971919719097188971879718697185971849718397182971819718097178971779717697175971749717397172971719717097168971679716697165971649716397162971619716097158971579715697155971549715397152971519715097148971479714697145971449714397142971419714097138971379713697135971349713397132971319713097128971279712697125971249712397122971219712097118971179711697115971149711397112971119711097108971079710697105971049710397102971019710097096970959709497093970929709197090970889708797086970859708497083970829708197080970789707797076970759707497073970729707197070970689706797066970659706497063970629706197060970589705797056970559705497053970529705197050970489704797046970459704497043970429704197040970389703797036970359703497033970329703197030970289702797026970259702497023970229702197020970189701797016970159701497013970129701197010970089700797006970059700497003970029700197000969689696796966969659696496963969629696196960969589695796956969559695496953969529695196950969489694796946969459694496943969429694196940969389693796936969359693496933969329693196930969289692796926969259692496923969229692196920969189691796916969159691496913969129691196910969089690796906969059690496903969029690196900968959689496893968929689196890968889688796886968859688496883968829688196880968789687796876968759687496873968729687196870968689686796866968659686496863968629686196860968589685796856968559685496853968529685196850968489684796846968459684496843968429684196840968389683796836968359683496833968329683196830968289682796826968259682496823968229682196820968189681796816968159681496813968129681196810968089680796806968059680496803968029680196800967959679496793967929679196790967889678796786967859678496783967829678196780967789677796776967759677496773967729677196770967689676796766967659676496763967629676196760967589675796756967559675496753967529675196750967489674796746967459674496743967429674196740967389673796736967359673496733967329673196730967289672796726967259672496723967229672196720967189671796716967159671496713967129671196710967089670796706967059670496703967029670196700966959669496693966929669196690966889668796686966859668496683966829668196680966789667796676966759667496673966729667196670966689666796666966659666496663966629666196660966589665796656966559665496653966529665196650966489664796646966459664496643966429664196640966389663796636966359663496633966329663196630966289662796626966259662496623966229662196620966189661796616966159661496613966129661196610966089660796606966059660496603966029660196600965959659496593965929659196590965889658796586965859658496583965829658196580965789657796576965759657496573965729657196570965689656796566965659656496563965629656196560965589655796556965559655496553965529655196550965489654796546965459654496543965429654196540965389653796536965359653496533965329653196530965289652796526965259652496523965229652196520965189651796516965159651496513965129651196510965089650796506965059650496503965029650196500964959649496493964929649196490964889648796486964859648496483964829648196480964789647796476964759647496473964729647196470964689646796466964659646496463964629646196460964589645796456964559645496453964529645196450964489644796446964459644496443964429644196440964389643796436964359643496433964329643196430964289642796426964259642496423964229642196420964189641796416964159641496413964129641196410964089640796406964059640496403964029640196400963959639496393963929639196390963889638796386963859638496383963829638196380963789637796376963759637496373963729637196370963689636796366963659636496363963629636196360963589635796356963559635496353963529635196350963489634796346963459634496343963429634196340963389633796336963359633496333963329633196330963289632796326963259632496323963229632196320963189631796316963159631496313963129631196310963089630796306963059630496303963029630196300962959629496293962929629196290962889628796286962859628496283962829628196280962789627796276962759627496273962729627196270962689626796266962659626496263962629626196260962589625796256962559625496253962529625196250962489624796246962459624496243962429624196240962389623796236962359623496233962329623196230962289622796226962259622496223962229622196220962189621796216962159621496213962129621196210962089620796206962059620496203962029620196200961959619496193961929619196190961889618796186961859618496183961829618196180961789617796176961759617496173961729617196170961689616796166961659616496163961629616196160961589615796156961559615496153961529615196150961489614796146961459614496143961429614196140961389613796136961359613496133961329613196130961289612796126961259612496123961229612196120961189611796116961159611496113961129611196110961089610796106961059610496103961029610196100960959609496093960929609196090960889608796086960859608496083960829608196080960789607796076960759607496073960729607196070960689606796066960659606496063960629606196060960589605796056960559605496053960529605196050960489604796046960459604496043960429604196040960389603796036960359603496033960329603196030960289602796026960259602496023960229602196020960189601796016960159601496013960129601196010960089600796006960059600496003960029600196000959589595795956959559595495953959529595195950959489594795946959459594495943959429594195940959389593795936959359593495933959329593195930959289592795926959259592495923959229592195920959189591795916959159591495913959129591195910959089590795906959059590495903959029590195900958949589395892958919589095888958879588695885958849588395882958819588095878958779587695875958749587395872958719587095868958679586695865958649586395862958619586095858958579585695855958549585395852958519585095848958479584695845958449584395842958419584095838958379583695835958349583395832958319583095828958279582695825958249582395822958219582095818958179581695815958149581395812958119581095808958079580695805958049580395802958019580095794957939579295791957909578895787957869578595784957839578295781957809577895777957769577595774957739577295771957709576895767957669576595764957639576295761957609575895757957569575595754957539575295751957509574895747957469574595744957439574295741957409573895737957369573595734957339573295731957309572895727957269572595724957239572295721957209571895717957169571595714957139571295711957109570895707957069570595704957039570295701957009569495693956929569195690956889568795686956859568495683956829568195680956789567795676956759567495673956729567195670956689566795666956659566495663956629566195660956589565795656956559565495653956529565195650956489564795646956459564495643956429564195640956389563795636956359563495633956329563195630956289562795626956259562495623956229562195620956189561795616956159561495613956129561195610956089560795606956059560495603956029560195600955949559395592955919559095588955879558695585955849558395582955819558095578955779557695575955749557395572955719557095568955679556695565955649556395562955619556095558955579555695555955549555395552955519555095548955479554695545955449554395542955419554095538955379553695535955349553395532955319553095528955279552695525955249552395522955219552095518955179551695515955149551395512955119551095508955079550695505955049550395502955019550095494954939549295491954909548895487954869548595484954839548295481954809547895477954769547595474954739547295471954709546895467954669546595464954639546295461954609545895457954569545595454954539545295451954509544895447954469544595444954439544295441954409543895437954369543595434954339543295431954309542895427954269542595424954239542295421954209541895417954169541595414954139541295411954109540895407954069540595404954039540295401954009539495393953929539195390953889538795386953859538495383953829538195380953789537795376953759537495373953729537195370953689536795366953659536495363953629536195360953589535795356953559535495353953529535195350953489534795346953459534495343953429534195340953389533795336953359533495333953329533195330953289532795326953259532495323953229532195320953189531795316953159531495313953129531195310953089530795306953059530495303953029530195300952949529395292952919529095288952879528695285952849528395282952819528095278952779527695275952749527395272952719527095268952679526695265952649526395262952619526095258952579525695255952549525395252952519525095248952479524695245952449524395242952419524095238952379523695235952349523395232952319523095228952279522695225952249522395222952219522095218952179521695215952149521395212952119521095208952079520695205952049520395202952019520095194951939519295191951909518895187951869518595184951839518295181951809517895177951769517595174951739517295171951709516895167951669516595164951639516295161951609515895157951569515595154951539515295151951509514895147951469514595144951439514295141951409513895137951369513595134951339513295131951309512895127951269512595124951239512295121951209511895117951169511595114951139511295111951109510895107951069510595104951039510295101951009509495093950929509195090950889508795086950859508495083950829508195080950789507795076950759507495073950729507195070950689506795066950659506495063950629506195060950589505795056950559505495053950529505195050950489504795046950459504495043950429504195040950389503795036950359503495033950329503195030950289502795026950259502495023950229502195020950189501795016950159501495013950129501195010950089500795006950059500495003950029500195000949489494794946949459494494943949429494194940949389493794936949359493494933949329493194930949289492794926949259492494923949229492194920949189491794916949159491494913949129491194910949089490794906949059490494903949029490194900948939489294891948909488894887948869488594884948839488294881948809487894877948769487594874948739487294871948709486894867948669486594864948639486294861948609485894857948569485594854948539485294851948509484894847948469484594844948439484294841948409483894837948369483594834948339483294831948309482894827948269482594824948239482294821948209481894817948169481594814948139481294811948109480894807948069480594804948039480294801948009479394792947919479094788947879478694785947849478394782947819478094778947779477694775947749477394772947719477094768947679476694765947649476394762947619476094758947579475694755947549475394752947519475094748947479474694745947449474394742947419474094738947379473694735947349473394732947319473094728947279472694725947249472394722947219472094718947179471694715947149471394712947119471094708947079470694705947049470394702947019470094693946929469194690946889468794686946859468494683946829468194680946789467794676946759467494673946729467194670946689466794666946659466494663946629466194660946589465794656946559465494653946529465194650946489464794646946459464494643946429464194640946389463794636946359463494633946329463194630946289462794626946259462494623946229462194620946189461794616946159461494613946129461194610946089460794606946059460494603946029460194600945939459294591945909458894587945869458594584945839458294581945809457894577945769457594574945739457294571945709456894567945669456594564945639456294561945609455894557945569455594554945539455294551945509454894547945469454594544945439454294541945409453894537945369453594534945339453294531945309452894527945269452594524945239452294521945209451894517945169451594514945139451294511945109450894507945069450594504945039450294501945009449394492944919449094488944879448694485944849448394482944819448094478944779447694475944749447394472944719447094468944679446694465944649446394462944619446094458944579445694455944549445394452944519445094448944479444694445944449444394442944419444094438944379443694435944349443394432944319443094428944279442694425944249442394422944219442094418944179441694415944149441394412944119441094408944079440694405944049440394402944019440094393943929439194390943889438794386943859438494383943829438194380943789437794376943759437494373943729437194370943689436794366943659436494363943629436194360943589435794356943559435494353943529435194350943489434794346943459434494343943429434194340943389433794336943359433494333943329433194330943289432794326943259432494323943229432194320943189431794316943159431494313943129431194310943089430794306943059430494303943029430194300942939429294291942909428894287942869428594284942839428294281942809427894277942769427594274942739427294271942709426894267942669426594264942639426294261942609425894257942569425594254942539425294251942509424894247942469424594244942439424294241942409423894237942369423594234942339423294231942309422894227942269422594224942239422294221942209421894217942169421594214942139421294211942109420894207942069420594204942039420294201942009419394192941919419094188941879418694185941849418394182941819418094178941779417694175941749417394172941719417094168941679416694165941649416394162941619416094158941579415694155941549415394152941519415094148941479414694145941449414394142941419414094138941379413694135941349413394132941319413094128941279412694125941249412394122941219412094118941179411694115941149411394112941119411094108941079410694105941049410394102941019410094093940929409194090940889408794086940859408494083940829408194080940789407794076940759407494073940729407194070940689406794066940659406494063940629406194060940589405794056940559405494053940529405194050940489404794046940459404494043940429404194040940389403794036940359403494033940329403194030940289402794026940259402494023940229402194020940189401794016940159401494013940129401194010940089400794006940059400494003940029400194000939389393793936939359393493933939329393193930939289392793926939259392493923939229392193920939189391793916939159391493913939129391193910939089390793906939059390493903939029390193900938929389193890938889388793886938859388493883938829388193880938789387793876938759387493873938729387193870938689386793866938659386493863938629386193860938589385793856938559385493853938529385193850938489384793846938459384493843938429384193840938389383793836938359383493833938329383193830938289382793826938259382493823938229382193820938189381793816938159381493813938129381193810938089380793806938059380493803938029380193800937929379193790937889378793786937859378493783937829378193780937789377793776937759377493773937729377193770937689376793766937659376493763937629376193760937589375793756937559375493753937529375193750937489374793746937459374493743937429374193740937389373793736937359373493733937329373193730937289372793726937259372493723937229372193720937189371793716937159371493713937129371193710937089370793706937059370493703937029370193700936929369193690936889368793686936859368493683936829368193680936789367793676936759367493673936729367193670936689366793666936659366493663936629366193660936589365793656936559365493653936529365193650936489364793646936459364493643936429364193640936389363793636936359363493633936329363193630936289362793626936259362493623936229362193620936189361793616936159361493613936129361193610936089360793606936059360493603936029360193600935929359193590935889358793586935859358493583935829358193580935789357793576935759357493573935729357193570935689356793566935659356493563935629356193560935589355793556935559355493553935529355193550935489354793546935459354493543935429354193540935389353793536935359353493533935329353193530935289352793526935259352493523935229352193520935189351793516935159351493513935129351193510935089350793506935059350493503935029350193500934929349193490934889348793486934859348493483934829348193480934789347793476934759347493473934729347193470934689346793466934659346493463934629346193460934589345793456934559345493453934529345193450934489344793446934459344493443934429344193440934389343793436934359343493433934329343193430934289342793426934259342493423934229342193420934189341793416934159341493413934129341193410934089340793406934059340493403934029340193400933929339193390933889338793386933859338493383933829338193380933789337793376933759337493373933729337193370933689336793366933659336493363933629336193360933589335793356933559335493353933529335193350933489334793346933459334493343933429334193340933389333793336933359333493333933329333193330933289332793326933259332493323933229332193320933189331793316933159331493313933129331193310933089330793306933059330493303933029330193300932929329193290932889328793286932859328493283932829328193280932789327793276932759327493273932729327193270932689326793266932659326493263932629326193260932589325793256932559325493253932529325193250932489324793246932459324493243932429324193240932389323793236932359323493233932329323193230932289322793226932259322493223932229322193220932189321793216932159321493213932129321193210932089320793206932059320493203932029320193200931929319193190931889318793186931859318493183931829318193180931789317793176931759317493173931729317193170931689316793166931659316493163931629316193160931589315793156931559315493153931529315193150931489314793146931459314493143931429314193140931389313793136931359313493133931329313193130931289312793126931259312493123931229312193120931189311793116931159311493113931129311193110931089310793106931059310493103931029310193100930929309193090930889308793086930859308493083930829308193080930789307793076930759307493073930729307193070930689306793066930659306493063930629306193060930589305793056930559305493053930529305193050930489304793046930459304493043930429304193040930389303793036930359303493033930329303193030930289302793026930259302493023930229302193020930189301793016930159301493013930129301193010930089300793006930059300493003930029300193000929289292792926929259292492923929229292192920929189291792916929159291492913929129291192910929089290792906929059290492903929029290192900928919289092888928879288692885928849288392882928819288092878928779287692875928749287392872928719287092868928679286692865928649286392862928619286092858928579285692855928549285392852928519285092848928479284692845928449284392842928419284092838928379283692835928349283392832928319283092828928279282692825928249282392822928219282092818928179281692815928149281392812928119281092808928079280692805928049280392802928019280092791927909278892787927869278592784927839278292781927809277892777927769277592774927739277292771927709276892767927669276592764927639276292761927609275892757927569275592754927539275292751927509274892747927469274592744927439274292741927409273892737927369273592734927339273292731927309272892727927269272592724927239272292721927209271892717927169271592714927139271292711927109270892707927069270592704927039270292701927009269192690926889268792686926859268492683926829268192680926789267792676926759267492673926729267192670926689266792666926659266492663926629266192660926589265792656926559265492653926529265192650926489264792646926459264492643926429264192640926389263792636926359263492633926329263192630926289262792626926259262492623926229262192620926189261792616926159261492613926129261192610926089260792606926059260492603926029260192600925919259092588925879258692585925849258392582925819258092578925779257692575925749257392572925719257092568925679256692565925649256392562925619256092558925579255692555925549255392552925519255092548925479254692545925449254392542925419254092538925379253692535925349253392532925319253092528925279252692525925249252392522925219252092518925179251692515925149251392512925119251092508925079250692505925049250392502925019250092491924909248892487924869248592484924839248292481924809247892477924769247592474924739247292471924709246892467924669246592464924639246292461924609245892457924569245592454924539245292451924509244892447924469244592444924439244292441924409243892437924369243592434924339243292431924309242892427924269242592424924239242292421924209241892417924169241592414924139241292411924109240892407924069240592404924039240292401924009239192390923889238792386923859238492383923829238192380923789237792376923759237492373923729237192370923689236792366923659236492363923629236192360923589235792356923559235492353923529235192350923489234792346923459234492343923429234192340923389233792336923359233492333923329233192330923289232792326923259232492323923229232192320923189231792316923159231492313923129231192310923089230792306923059230492303923029230192300922919229092288922879228692285922849228392282922819228092278922779227692275922749227392272922719227092268922679226692265922649226392262922619226092258922579225692255922549225392252922519225092248922479224692245922449224392242922419224092238922379223692235922349223392232922319223092228922279222692225922249222392222922219222092218922179221692215922149221392212922119221092208922079220692205922049220392202922019220092191921909218892187921869218592184921839218292181921809217892177921769217592174921739217292171921709216892167921669216592164921639216292161921609215892157921569215592154921539215292151921509214892147921469214592144921439214292141921409213892137921369213592134921339213292131921309212892127921269212592124921239212292121921209211892117921169211592114921139211292111921109210892107921069210592104921039210292101921009209192090920889208792086920859208492083920829208192080920789207792076920759207492073920729207192070920689206792066920659206492063920629206192060920589205792056920559205492053920529205192050920489204792046920459204492043920429204192040920389203792036920359203492033920329203192030920289202792026920259202492023920229202192020920189201792016920159201492013920129201192010920089200792006920059200492003920029200192000919189191791916919159191491913919129191191910919089190791906919059190491903919029190191900918909188891887918869188591884918839188291881918809187891877918769187591874918739187291871918709186891867918669186591864918639186291861918609185891857918569185591854918539185291851918509184891847918469184591844918439184291841918409183891837918369183591834918339183291831918309182891827918269182591824918239182291821918209181891817918169181591814918139181291811918109180891807918069180591804918039180291801918009179091788917879178691785917849178391782917819178091778917779177691775917749177391772917719177091768917679176691765917649176391762917619176091758917579175691755917549175391752917519175091748917479174691745917449174391742917419174091738917379173691735917349173391732917319173091728917279172691725917249172391722917219172091718917179171691715917149171391712917119171091708917079170691705917049170391702917019170091690916889168791686916859168491683916829168191680916789167791676916759167491673916729167191670916689166791666916659166491663916629166191660916589165791656916559165491653916529165191650916489164791646916459164491643916429164191640916389163791636916359163491633916329163191630916289162791626916259162491623916229162191620916189161791616916159161491613916129161191610916089160791606916059160491603916029160191600915909158891587915869158591584915839158291581915809157891577915769157591574915739157291571915709156891567915669156591564915639156291561915609155891557915569155591554915539155291551915509154891547915469154591544915439154291541915409153891537915369153591534915339153291531915309152891527915269152591524915239152291521915209151891517915169151591514915139151291511915109150891507915069150591504915039150291501915009149091488914879148691485914849148391482914819148091478914779147691475914749147391472914719147091468914679146691465914649146391462914619146091458914579145691455914549145391452914519145091448914479144691445914449144391442914419144091438914379143691435914349143391432914319143091428914279142691425914249142391422914219142091418914179141691415914149141391412914119141091408914079140691405914049140391402914019140091390913889138791386913859138491383913829138191380913789137791376913759137491373913729137191370913689136791366913659136491363913629136191360913589135791356913559135491353913529135191350913489134791346913459134491343913429134191340913389133791336913359133491333913329133191330913289132791326913259132491323913229132191320913189131791316913159131491313913129131191310913089130791306913059130491303913029130191300912909128891287912869128591284912839128291281912809127891277912769127591274912739127291271912709126891267912669126591264912639126291261912609125891257912569125591254912539125291251912509124891247912469124591244912439124291241912409123891237912369123591234912339123291231912309122891227912269122591224912239122291221912209121891217912169121591214912139121291211912109120891207912069120591204912039120291201912009119091188911879118691185911849118391182911819118091178911779117691175911749117391172911719117091168911679116691165911649116391162911619116091158911579115691155911549115391152911519115091148911479114691145911449114391142911419114091138911379113691135911349113391132911319113091128911279112691125911249112391122911219112091118911179111691115911149111391112911119111091108911079110691105911049110391102911019110091090910889108791086910859108491083910829108191080910789107791076910759107491073910729107191070910689106791066910659106491063910629106191060910589105791056910559105491053910529105191050910489104791046910459104491043910429104191040910389103791036910359103491033910329103191030910289102791026910259102491023910229102191020910189101791016910159101491013910129101191010910089100791006910059100491003910029100191000909089090790906909059090490903909029090190900908889088790886908859088490883908829088190880908789087790876908759087490873908729087190870908689086790866908659086490863908629086190860908589085790856908559085490853908529085190850908489084790846908459084490843908429084190840908389083790836908359083490833908329083190830908289082790826908259082490823908229082190820908189081790816908159081490813908129081190810908089080790806908059080490803908029080190800907889078790786907859078490783907829078190780907789077790776907759077490773907729077190770907689076790766907659076490763907629076190760907589075790756907559075490753907529075190750907489074790746907459074490743907429074190740907389073790736907359073490733907329073190730907289072790726907259072490723907229072190720907189071790716907159071490713907129071190710907089070790706907059070490703907029070190700906889068790686906859068490683906829068190680906789067790676906759067490673906729067190670906689066790666906659066490663906629066190660906589065790656906559065490653906529065190650906489064790646906459064490643906429064190640906389063790636906359063490633906329063190630906289062790626906259062490623906229062190620906189061790616906159061490613906129061190610906089060790606906059060490603906029060190600905889058790586905859058490583905829058190580905789057790576905759057490573905729057190570905689056790566905659056490563905629056190560905589055790556905559055490553905529055190550905489054790546905459054490543905429054190540905389053790536905359053490533905329053190530905289052790526905259052490523905229052190520905189051790516905159051490513905129051190510905089050790506905059050490503905029050190500904889048790486904859048490483904829048190480904789047790476904759047490473904729047190470904689046790466904659046490463904629046190460904589045790456904559045490453904529045190450904489044790446904459044490443904429044190440904389043790436904359043490433904329043190430904289042790426904259042490423904229042190420904189041790416904159041490413904129041190410904089040790406904059040490403904029040190400903889038790386903859038490383903829038190380903789037790376903759037490373903729037190370903689036790366903659036490363903629036190360903589035790356903559035490353903529035190350903489034790346903459034490343903429034190340903389033790336903359033490333903329033190330903289032790326903259032490323903229032190320903189031790316903159031490313903129031190310903089030790306903059030490303903029030190300902889028790286902859028490283902829028190280902789027790276902759027490273902729027190270902689026790266902659026490263902629026190260902589025790256902559025490253902529025190250902489024790246902459024490243902429024190240902389023790236902359023490233902329023190230902289022790226902259022490223902229022190220902189021790216902159021490213902129021190210902089020790206902059020490203902029020190200901889018790186901859018490183901829018190180901789017790176901759017490173901729017190170901689016790166901659016490163901629016190160901589015790156901559015490153901529015190150901489014790146901459014490143901429014190140901389013790136901359013490133901329013190130901289012790126901259012490123901229012190120901189011790116901159011490113901129011190110901089010790106901059010490103901029010190100900889008790086900859008490083900829008190080900789007790076900759007490073900729007190070900689006790066900659006490063900629006190060900589005790056900559005490053900529005190050900489004790046900459004490043900429004190040900389003790036900359003490033900329003190030900289002790026900259002490023900229002190020900189001790016900159001490013900129001190010900089000790006900059000490003900029000190000888887888868888588884888838888288881888808887788876888758887488873888728887188870888678886688865888648886388862888618886088857888568885588854888538885288851888508884788846888458884488843888428884188840888378883688835888348883388832888318883088827888268882588824888238882288821888208881788816888158881488813888128881188810888078880688805888048880388802888018880088787887868878588784887838878288781887808877788776887758877488773887728877188770887678876688765887648876388762887618876088757887568875588754887538875288751887508874788746887458874488743887428874188740887378873688735887348873388732887318873088727887268872588724887238872288721887208871788716887158871488713887128871188710887078870688705887048870388702887018870088687886868868588684886838868288681886808867788676886758867488673886728867188670886678866688665886648866388662886618866088657886568865588654886538865288651886508864788646886458864488643886428864188640886378863688635886348863388632886318863088627886268862588624886238862288621886208861788616886158861488613886128861188610886078860688605886048860388602886018860088587885868858588584885838858288581885808857788576885758857488573885728857188570885678856688565885648856388562885618856088557885568855588554885538855288551885508854788546885458854488543885428854188540885378853688535885348853388532885318853088527885268852588524885238852288521885208851788516885158851488513885128851188510885078850688505885048850388502885018850088487884868848588484884838848288481884808847788476884758847488473884728847188470884678846688465884648846388462884618846088457884568845588454884538845288451884508844788446884458844488443884428844188440884378843688435884348843388432884318843088427884268842588424884238842288421884208841788416884158841488413884128841188410884078840688405884048840388402884018840088387883868838588384883838838288381883808837788376883758837488373883728837188370883678836688365883648836388362883618836088357883568835588354883538835288351883508834788346883458834488343883428834188340883378833688335883348833388332883318833088327883268832588324883238832288321883208831788316883158831488313883128831188310883078830688305883048830388302883018830088287882868828588284882838828288281882808827788276882758827488273882728827188270882678826688265882648826388262882618826088257882568825588254882538825288251882508824788246882458824488243882428824188240882378823688235882348823388232882318823088227882268822588224882238822288221882208821788216882158821488213882128821188210882078820688205882048820388202882018820088187881868818588184881838818288181881808817788176881758817488173881728817188170881678816688165881648816388162881618816088157881568815588154881538815288151881508814788146881458814488143881428814188140881378813688135881348813388132881318813088127881268812588124881238812288121881208811788116881158811488113881128811188110881078810688105881048810388102881018810088087880868808588084880838808288081880808807788076880758807488073880728807188070880678806688065880648806388062880618806088057880568805588054880538805288051880508804788046880458804488043880428804188040880378803688035880348803388032880318803088027880268802588024880238802288021880208801788016880158801488013880128801188010880078800688005880048800388002880018800087877878768787587874878738787287871878708786787866878658786487863878628786187860878578785687855878548785387852878518785087847878468784587844878438784287841878408783787836878358783487833878328783187830878278782687825878248782387822878218782087817878168781587814878138781287811878108780787806878058780487803878028780187800877868778587784877838778287781877808777787776877758777487773877728777187770877678776687765877648776387762877618776087757877568775587754877538775287751877508774787746877458774487743877428774187740877378773687735877348773387732877318773087727877268772587724877238772287721877208771787716877158771487713877128771187710877078770687705877048770387702877018770087686876858768487683876828768187680876778767687675876748767387672876718767087667876668766587664876638766287661876608765787656876558765487653876528765187650876478764687645876448764387642876418764087637876368763587634876338763287631876308762787626876258762487623876228762187620876178761687615876148761387612876118761087607876068760587604876038760287601876008758687585875848758387582875818758087577875768757587574875738757287571875708756787566875658756487563875628756187560875578755687555875548755387552875518755087547875468754587544875438754287541875408753787536875358753487533875328753187530875278752687525875248752387522875218752087517875168751587514875138751287511875108750787506875058750487503875028750187500874868748587484874838748287481874808747787476874758747487473874728747187470874678746687465874648746387462874618746087457874568745587454874538745287451874508744787446874458744487443874428744187440874378743687435874348743387432874318743087427874268742587424874238742287421874208741787416874158741487413874128741187410874078740687405874048740387402874018740087386873858738487383873828738187380873778737687375873748737387372873718737087367873668736587364873638736287361873608735787356873558735487353873528735187350873478734687345873448734387342873418734087337873368733587334873338733287331873308732787326873258732487323873228732187320873178731687315873148731387312873118731087307873068730587304873038730287301873008728687285872848728387282872818728087277872768727587274872738727287271872708726787266872658726487263872628726187260872578725687255872548725387252872518725087247872468724587244872438724287241872408723787236872358723487233872328723187230872278722687225872248722387222872218722087217872168721587214872138721287211872108720787206872058720487203872028720187200871868718587184871838718287181871808717787176871758717487173871728717187170871678716687165871648716387162871618716087157871568715587154871538715287151871508714787146871458714487143871428714187140871378713687135871348713387132871318713087127871268712587124871238712287121871208711787116871158711487113871128711187110871078710687105871048710387102871018710087086870858708487083870828708187080870778707687075870748707387072870718707087067870668706587064870638706287061870608705787056870558705487053870528705187050870478704687045870448704387042870418704087037870368703587034870338703287031870308702787026870258702487023870228702187020870178701687015870148701387012870118701087007870068700587004870038700287001870008686786866868658686486863868628686186860868578685686855868548685386852868518685086847868468684586844868438684286841868408683786836868358683486833868328683186830868278682686825868248682386822868218682086817868168681586814868138681286811868108680786806868058680486803868028680186800867858678486783867828678186780867778677686775867748677386772867718677086767867668676586764867638676286761867608675786756867558675486753867528675186750867478674686745867448674386742867418674086737867368673586734867338673286731867308672786726867258672486723867228672186720867178671686715867148671386712867118671086707867068670586704867038670286701867008668586684866838668286681866808667786676866758667486673866728667186670866678666686665866648666386662866618666086657866568665586654866538665286651866508664786646866458664486643866428664186640866378663686635866348663386632866318663086627866268662586624866238662286621866208661786616866158661486613866128661186610866078660686605866048660386602866018660086585865848658386582865818658086577865768657586574865738657286571865708656786566865658656486563865628656186560865578655686555865548655386552865518655086547865468654586544865438654286541865408653786536865358653486533865328653186530865278652686525865248652386522865218652086517865168651586514865138651286511865108650786506865058650486503865028650186500864858648486483864828648186480864778647686475864748647386472864718647086467864668646586464864638646286461864608645786456864558645486453864528645186450864478644686445864448644386442864418644086437864368643586434864338643286431864308642786426864258642486423864228642186420864178641686415864148641386412864118641086407864068640586404864038640286401864008638586384863838638286381863808637786376863758637486373863728637186370863678636686365863648636386362863618636086357863568635586354863538635286351863508634786346863458634486343863428634186340863378633686335863348633386332863318633086327863268632586324863238632286321863208631786316863158631486313863128631186310863078630686305863048630386302863018630086285862848628386282862818628086277862768627586274862738627286271862708626786266862658626486263862628626186260862578625686255862548625386252862518625086247862468624586244862438624286241862408623786236862358623486233862328623186230862278622686225862248622386222862218622086217862168621586214862138621286211862108620786206862058620486203862028620186200861858618486183861828618186180861778617686175861748617386172861718617086167861668616586164861638616286161861608615786156861558615486153861528615186150861478614686145861448614386142861418614086137861368613586134861338613286131861308612786126861258612486123861228612186120861178611686115861148611386112861118611086107861068610586104861038610286101861008608586084860838608286081860808607786076860758607486073860728607186070860678606686065860648606386062860618606086057860568605586054860538605286051860508604786046860458604486043860428604186040860378603686035860348603386032860318603086027860268602586024860238602286021860208601786016860158601486013860128601186010860078600686005860048600386002860018600085857858568585585854858538585285851858508584785846858458584485843858428584185840858378583685835858348583385832858318583085827858268582585824858238582285821858208581785816858158581485813858128581185810858078580685805858048580385802858018580085784857838578285781857808577785776857758577485773857728577185770857678576685765857648576385762857618576085757857568575585754857538575285751857508574785746857458574485743857428574185740857378573685735857348573385732857318573085727857268572585724857238572285721857208571785716857158571485713857128571185710857078570685705857048570385702857018570085684856838568285681856808567785676856758567485673856728567185670856678566685665856648566385662856618566085657856568565585654856538565285651856508564785646856458564485643856428564185640856378563685635856348563385632856318563085627856268562585624856238562285621856208561785616856158561485613856128561185610856078560685605856048560385602856018560085584855838558285581855808557785576855758557485573855728557185570855678556685565855648556385562855618556085557855568555585554855538555285551855508554785546855458554485543855428554185540855378553685535855348553385532855318553085527855268552585524855238552285521855208551785516855158551485513855128551185510855078550685505855048550385502855018550085484854838548285481854808547785476854758547485473854728547185470854678546685465854648546385462854618546085457854568545585454854538545285451854508544785446854458544485443854428544185440854378543685435854348543385432854318543085427854268542585424854238542285421854208541785416854158541485413854128541185410854078540685405854048540385402854018540085384853838538285381853808537785376853758537485373853728537185370853678536685365853648536385362853618536085357853568535585354853538535285351853508534785346853458534485343853428534185340853378533685335853348533385332853318533085327853268532585324853238532285321853208531785316853158531485313853128531185310853078530685305853048530385302853018530085284852838528285281852808527785276852758527485273852728527185270852678526685265852648526385262852618526085257852568525585254852538525285251852508524785246852458524485243852428524185240852378523685235852348523385232852318523085227852268522585224852238522285221852208521785216852158521485213852128521185210852078520685205852048520385202852018520085184851838518285181851808517785176851758517485173851728517185170851678516685165851648516385162851618516085157851568515585154851538515285151851508514785146851458514485143851428514185140851378513685135851348513385132851318513085127851268512585124851238512285121851208511785116851158511485113851128511185110851078510685105851048510385102851018510085084850838508285081850808507785076850758507485073850728507185070850678506685065850648506385062850618506085057850568505585054850538505285051850508504785046850458504485043850428504185040850378503685035850348503385032850318503085027850268502585024850238502285021850208501785016850158501485013850128501185010850078500685005850048500385002850018500084847848468484584844848438484284841848408483784836848358483484833848328483184830848278482684825848248482384822848218482084817848168481584814848138481284811848108480784806848058480484803848028480184800847838478284781847808477784776847758477484773847728477184770847678476684765847648476384762847618476084757847568475584754847538475284751847508474784746847458474484743847428474184740847378473684735847348473384732847318473084727847268472584724847238472284721847208471784716847158471484713847128471184710847078470684705847048470384702847018470084683846828468184680846778467684675846748467384672846718467084667846668466584664846638466284661846608465784656846558465484653846528465184650846478464684645846448464384642846418464084637846368463584634846338463284631846308462784626846258462484623846228462184620846178461684615846148461384612846118461084607846068460584604846038460284601846008458384582845818458084577845768457584574845738457284571845708456784566845658456484563845628456184560845578455684555845548455384552845518455084547845468454584544845438454284541845408453784536845358453484533845328453184530845278452684525845248452384522845218452084517845168451584514845138451284511845108450784506845058450484503845028450184500844838448284481844808447784476844758447484473844728447184470844678446684465844648446384462844618446084457844568445584454844538445284451844508444784446844458444484443844428444184440844378443684435844348443384432844318443084427844268442584424844238442284421844208441784416844158441484413844128441184410844078440684405844048440384402844018440084383843828438184380843778437684375843748437384372843718437084367843668436584364843638436284361843608435784356843558435484353843528435184350843478434684345843448434384342843418434084337843368433584334843338433284331843308432784326843258432484323843228432184320843178431684315843148431384312843118431084307843068430584304843038430284301843008428384282842818428084277842768427584274842738427284271842708426784266842658426484263842628426184260842578425684255842548425384252842518425084247842468424584244842438424284241842408423784236842358423484233842328423184230842278422684225842248422384222842218422084217842168421584214842138421284211842108420784206842058420484203842028420184200841838418284181841808417784176841758417484173841728417184170841678416684165841648416384162841618416084157841568415584154841538415284151841508414784146841458414484143841428414184140841378413684135841348413384132841318413084127841268412584124841238412284121841208411784116841158411484113841128411184110841078410684105841048410384102841018410084083840828408184080840778407684075840748407384072840718407084067840668406584064840638406284061840608405784056840558405484053840528405184050840478404684045840448404384042840418404084037840368403584034840338403284031840308402784026840258402484023840228402184020840178401684015840148401384012840118401084007840068400584004840038400284001840008383783836838358383483833838328383183830838278382683825838248382383822838218382083817838168381583814838138381283811838108380783806838058380483803838028380183800837828378183780837778377683775837748377383772837718377083767837668376583764837638376283761837608375783756837558375483753837528375183750837478374683745837448374383742837418374083737837368373583734837338373283731837308372783726837258372483723837228372183720837178371683715837148371383712837118371083707837068370583704837038370283701837008368283681836808367783676836758367483673836728367183670836678366683665836648366383662836618366083657836568365583654836538365283651836508364783646836458364483643836428364183640836378363683635836348363383632836318363083627836268362583624836238362283621836208361783616836158361483613836128361183610836078360683605836048360383602836018360083582835818358083577835768357583574835738357283571835708356783566835658356483563835628356183560835578355683555835548355383552835518355083547835468354583544835438354283541835408353783536835358353483533835328353183530835278352683525835248352383522835218352083517835168351583514835138351283511835108350783506835058350483503835028350183500834828348183480834778347683475834748347383472834718347083467834668346583464834638346283461834608345783456834558345483453834528345183450834478344683445834448344383442834418344083437834368343583434834338343283431834308342783426834258342483423834228342183420834178341683415834148341383412834118341083407834068340583404834038340283401834008338283381833808337783376833758337483373833728337183370833678336683365833648336383362833618336083357833568335583354833538335283351833508334783346833458334483343833428334183340833378333683335833348333383332833318333083327833268332583324833238332283321833208331783316833158331483313833128331183310833078330683305833048330383302833018330083282832818328083277832768327583274832738327283271832708326783266832658326483263832628326183260832578325683255832548325383252832518325083247832468324583244832438324283241832408323783236832358323483233832328323183230832278322683225832248322383222832218322083217832168321583214832138321283211832108320783206832058320483203832028320183200831828318183180831778317683175831748317383172831718317083167831668316583164831638316283161831608315783156831558315483153831528315183150831478314683145831448314383142831418314083137831368313583134831338313283131831308312783126831258312483123831228312183120831178311683115831148311383112831118311083107831068310583104831038310283101831008308283081830808307783076830758307483073830728307183070830678306683065830648306383062830618306083057830568305583054830538305283051830508304783046830458304483043830428304183040830378303683035830348303383032830318303083027830268302583024830238302283021830208301783016830158301483013830128301183010830078300683005830048300383002830018300082827828268282582824828238282282821828208281782816828158281482813828128281182810828078280682805828048280382802828018280082781827808277782776827758277482773827728277182770827678276682765827648276382762827618276082757827568275582754827538275282751827508274782746827458274482743827428274182740827378273682735827348273382732827318273082727827268272582724827238272282721827208271782716827158271482713827128271182710827078270682705827048270382702827018270082681826808267782676826758267482673826728267182670826678266682665826648266382662826618266082657826568265582654826538265282651826508264782646826458264482643826428264182640826378263682635826348263382632826318263082627826268262582624826238262282621826208261782616826158261482613826128261182610826078260682605826048260382602826018260082581825808257782576825758257482573825728257182570825678256682565825648256382562825618256082557825568255582554825538255282551825508254782546825458254482543825428254182540825378253682535825348253382532825318253082527825268252582524825238252282521825208251782516825158251482513825128251182510825078250682505825048250382502825018250082481824808247782476824758247482473824728247182470824678246682465824648246382462824618246082457824568245582454824538245282451824508244782446824458244482443824428244182440824378243682435824348243382432824318243082427824268242582424824238242282421824208241782416824158241482413824128241182410824078240682405824048240382402824018240082381823808237782376823758237482373823728237182370823678236682365823648236382362823618236082357823568235582354823538235282351823508234782346823458234482343823428234182340823378233682335823348233382332823318233082327823268232582324823238232282321823208231782316823158231482313823128231182310823078230682305823048230382302823018230082281822808227782276822758227482273822728227182270822678226682265822648226382262822618226082257822568225582254822538225282251822508224782246822458224482243822428224182240822378223682235822348223382232822318223082227822268222582224822238222282221822208221782216822158221482213822128221182210822078220682205822048220382202822018220082181821808217782176821758217482173821728217182170821678216682165821648216382162821618216082157821568215582154821538215282151821508214782146821458214482143821428214182140821378213682135821348213382132821318213082127821268212582124821238212282121821208211782116821158211482113821128211182110821078210682105821048210382102821018210082081820808207782076820758207482073820728207182070820678206682065820648206382062820618206082057820568205582054820538205282051820508204782046820458204482043820428204182040820378203682035820348203382032820318203082027820268202582024820238202282021820208201782016820158201482013820128201182010820078200682005820048200382002820018200081817818168181581814818138181281811818108180781806818058180481803818028180181800817808177781776817758177481773817728177181770817678176681765817648176381762817618176081757817568175581754817538175281751817508174781746817458174481743817428174181740817378173681735817348173381732817318173081727817268172581724817238172281721817208171781716817158171481713817128171181710817078170681705817048170381702817018170081680816778167681675816748167381672816718167081667816668166581664816638166281661816608165781656816558165481653816528165181650816478164681645816448164381642816418164081637816368163581634816338163281631816308162781626816258162481623816228162181620816178161681615816148161381612816118161081607816068160581604816038160281601816008158081577815768157581574815738157281571815708156781566815658156481563815628156181560815578155681555815548155381552815518155081547815468154581544815438154281541815408153781536815358153481533815328153181530815278152681525815248152381522815218152081517815168151581514815138151281511815108150781506815058150481503815028150181500814808147781476814758147481473814728147181470814678146681465814648146381462814618146081457814568145581454814538145281451814508144781446814458144481443814428144181440814378143681435814348143381432814318143081427814268142581424814238142281421814208141781416814158141481413814128141181410814078140681405814048140381402814018140081380813778137681375813748137381372813718137081367813668136581364813638136281361813608135781356813558135481353813528135181350813478134681345813448134381342813418134081337813368133581334813338133281331813308132781326813258132481323813228132181320813178131681315813148131381312813118131081307813068130581304813038130281301813008128081277812768127581274812738127281271812708126781266812658126481263812628126181260812578125681255812548125381252812518125081247812468124581244812438124281241812408123781236812358123481233812328123181230812278122681225812248122381222812218122081217812168121581214812138121281211812108120781206812058120481203812028120181200811808117781176811758117481173811728117181170811678116681165811648116381162811618116081157811568115581154811538115281151811508114781146811458114481143811428114181140811378113681135811348113381132811318113081127811268112581124811238112281121811208111781116811158111481113811128111181110811078110681105811048110381102811018110081080810778107681075810748107381072810718107081067810668106581064810638106281061810608105781056810558105481053810528105181050810478104681045810448104381042810418104081037810368103581034810338103281031810308102781026810258102481023810228102181020810178101681015810148101381012810118101081007810068100581004810038100281001810008080780806808058080480803808028080180800807778077680775807748077380772807718077080767807668076580764807638076280761807608075780756807558075480753807528075180750807478074680745807448074380742807418074080737807368073580734807338073280731807308072780726807258072480723807228072180720807178071680715807148071380712807118071080707807068070580704807038070280701807008067780676806758067480673806728067180670806678066680665806648066380662806618066080657806568065580654806538065280651806508064780646806458064480643806428064180640806378063680635806348063380632806318063080627806268062580624806238062280621806208061780616806158061480613806128061180610806078060680605806048060380602806018060080577805768057580574805738057280571805708056780566805658056480563805628056180560805578055680555805548055380552805518055080547805468054580544805438054280541805408053780536805358053480533805328053180530805278052680525805248052380522805218052080517805168051580514805138051280511805108050780506805058050480503805028050180500804778047680475804748047380472804718047080467804668046580464804638046280461804608045780456804558045480453804528045180450804478044680445804448044380442804418044080437804368043580434804338043280431804308042780426804258042480423804228042180420804178041680415804148041380412804118041080407804068040580404804038040280401804008037780376803758037480373803728037180370803678036680365803648036380362803618036080357803568035580354803538035280351803508034780346803458034480343803428034180340803378033680335803348033380332803318033080327803268032580324803238032280321803208031780316803158031480313803128031180310803078030680305803048030380302803018030080277802768027580274802738027280271802708026780266802658026480263802628026180260802578025680255802548025380252802518025080247802468024580244802438024280241802408023780236802358023480233802328023180230802278022680225802248022380222802218022080217802168021580214802138021280211802108020780206802058020480203802028020180200801778017680175801748017380172801718017080167801668016580164801638016280161801608015780156801558015480153801528015180150801478014680145801448014380142801418014080137801368013580134801338013280131801308012780126801258012480123801228012180120801178011680115801148011380112801118011080107801068010580104801038010280101801008007780076800758007480073800728007180070800678006680065800648006380062800618006080057800568005580054800538005280051800508004780046800458004480043800428004180040800378003680035800348003380032800318003080027800268002580024800238002280021800208001780016800158001480013800128001180010800078000680005800048000380002800018000077777677775777747777377772777717777077766777657776477763777627776177760777567775577754777537775277751777507774677745777447774377742777417774077736777357773477733777327773177730777267772577724777237772277721777207771677715777147771377712777117771077706777057770477703777027770177700776767767577674776737767277671776707766677665776647766377662776617766077656776557765477653776527765177650776467764577644776437764277641776407763677635776347763377632776317763077626776257762477623776227762177620776167761577614776137761277611776107760677605776047760377602776017760077576775757757477573775727757177570775667756577564775637756277561775607755677555775547755377552775517755077546775457754477543775427754177540775367753577534775337753277531775307752677525775247752377522775217752077516775157751477513775127751177510775067750577504775037750277501775007747677475774747747377472774717747077466774657746477463774627746177460774567745577454774537745277451774507744677445774447744377442774417744077436774357743477433774327743177430774267742577424774237742277421774207741677415774147741377412774117741077406774057740477403774027740177400773767737577374773737737277371773707736677365773647736377362773617736077356773557735477353773527735177350773467734577344773437734277341773407733677335773347733377332773317733077326773257732477323773227732177320773167731577314773137731277311773107730677305773047730377302773017730077276772757727477273772727727177270772667726577264772637726277261772607725677255772547725377252772517725077246772457724477243772427724177240772367723577234772337723277231772307722677225772247722377222772217722077216772157721477213772127721177210772067720577204772037720277201772007717677175771747717377172771717717077166771657716477163771627716177160771567715577154771537715277151771507714677145771447714377142771417714077136771357713477133771327713177130771267712577124771237712277121771207711677115771147711377112771117711077106771057710477103771027710177100770767707577074770737707277071770707706677065770647706377062770617706077056770557705477053770527705177050770467704577044770437704277041770407703677035770347703377032770317703077026770257702477023770227702177020770167701577014770137701277011770107700677005770047700377002770017700076766767657676476763767627676176760767567675576754767537675276751767507674676745767447674376742767417674076736767357673476733767327673176730767267672576724767237672276721767207671676715767147671376712767117671076706767057670476703767027670176700766757667476673766727667176670766667666576664766637666276661766607665676655766547665376652766517665076646766457664476643766427664176640766367663576634766337663276631766307662676625766247662376622766217662076616766157661476613766127661176610766067660576604766037660276601766007657576574765737657276571765707656676565765647656376562765617656076556765557655476553765527655176550765467654576544765437654276541765407653676535765347653376532765317653076526765257652476523765227652176520765167651576514765137651276511765107650676505765047650376502765017650076475764747647376472764717647076466764657646476463764627646176460764567645576454764537645276451764507644676445764447644376442764417644076436764357643476433764327643176430764267642576424764237642276421764207641676415764147641376412764117641076406764057640476403764027640176400763757637476373763727637176370763667636576364763637636276361763607635676355763547635376352763517635076346763457634476343763427634176340763367633576334763337633276331763307632676325763247632376322763217632076316763157631476313763127631176310763067630576304763037630276301763007627576274762737627276271762707626676265762647626376262762617626076256762557625476253762527625176250762467624576244762437624276241762407623676235762347623376232762317623076226762257622476223762227622176220762167621576214762137621276211762107620676205762047620376202762017620076175761747617376172761717617076166761657616476163761627616176160761567615576154761537615276151761507614676145761447614376142761417614076136761357613476133761327613176130761267612576124761237612276121761207611676115761147611376112761117611076106761057610476103761027610176100760757607476073760727607176070760667606576064760637606276061760607605676055760547605376052760517605076046760457604476043760427604176040760367603576034760337603276031760307602676025760247602376022760217602076016760157601476013760127601176010760067600576004760037600276001760007575675755757547575375752757517575075746757457574475743757427574175740757367573575734757337573275731757307572675725757247572375722757217572075716757157571475713757127571175710757067570575704757037570275701757007567475673756727567175670756667566575664756637566275661756607565675655756547565375652756517565075646756457564475643756427564175640756367563575634756337563275631756307562675625756247562375622756217562075616756157561475613756127561175610756067560575604756037560275601756007557475573755727557175570755667556575564755637556275561755607555675555755547555375552755517555075546755457554475543755427554175540755367553575534755337553275531755307552675525755247552375522755217552075516755157551475513755127551175510755067550575504755037550275501755007547475473754727547175470754667546575464754637546275461754607545675455754547545375452754517545075446754457544475443754427544175440754367543575434754337543275431754307542675425754247542375422754217542075416754157541475413754127541175410754067540575404754037540275401754007537475373753727537175370753667536575364753637536275361753607535675355753547535375352753517535075346753457534475343753427534175340753367533575334753337533275331753307532675325753247532375322753217532075316753157531475313753127531175310753067530575304753037530275301753007527475273752727527175270752667526575264752637526275261752607525675255752547525375252752517525075246752457524475243752427524175240752367523575234752337523275231752307522675225752247522375222752217522075216752157521475213752127521175210752067520575204752037520275201752007517475173751727517175170751667516575164751637516275161751607515675155751547515375152751517515075146751457514475143751427514175140751367513575134751337513275131751307512675125751247512375122751217512075116751157511475113751127511175110751067510575104751037510275101751007507475073750727507175070750667506575064750637506275061750607505675055750547505375052750517505075046750457504475043750427504175040750367503575034750337503275031750307502675025750247502375022750217502075016750157501475013750127501175010750067500575004750037500275001750007474674745747447474374742747417474074736747357473474733747327473174730747267472574724747237472274721747207471674715747147471374712747117471074706747057470474703747027470174700746737467274671746707466674665746647466374662746617466074656746557465474653746527465174650746467464574644746437464274641746407463674635746347463374632746317463074626746257462474623746227462174620746167461574614746137461274611746107460674605746047460374602746017460074573745727457174570745667456574564745637456274561745607455674555745547455374552745517455074546745457454474543745427454174540745367453574534745337453274531745307452674525745247452374522745217452074516745157451474513745127451174510745067450574504745037450274501745007447374472744717447074466744657446474463744627446174460744567445574454744537445274451744507444674445744447444374442744417444074436744357443474433744327443174430744267442574424744237442274421744207441674415744147441374412744117441074406744057440474403744027440174400743737437274371743707436674365743647436374362743617436074356743557435474353743527435174350743467434574344743437434274341743407433674335743347433374332743317433074326743257432474323743227432174320743167431574314743137431274311743107430674305743047430374302743017430074273742727427174270742667426574264742637426274261742607425674255742547425374252742517425074246742457424474243742427424174240742367423574234742337423274231742307422674225742247422374222742217422074216742157421474213742127421174210742067420574204742037420274201742007417374172741717417074166741657416474163741627416174160741567415574154741537415274151741507414674145741447414374142741417414074136741357413474133741327413174130741267412574124741237412274121741207411674115741147411374112741117411074106741057410474103741027410174100740737407274071740707406674065740647406374062740617406074056740557405474053740527405174050740467404574044740437404274041740407403674035740347403374032740317403074026740257402474023740227402174020740167401574014740137401274011740107400674005740047400374002740017400073736737357373473733737327373173730737267372573724737237372273721737207371673715737147371373712737117371073706737057370473703737027370173700736727367173670736667366573664736637366273661736607365673655736547365373652736517365073646736457364473643736427364173640736367363573634736337363273631736307362673625736247362373622736217362073616736157361473613736127361173610736067360573604736037360273601736007357273571735707356673565735647356373562735617356073556735557355473553735527355173550735467354573544735437354273541735407353673535735347353373532735317353073526735257352473523735227352173520735167351573514735137351273511735107350673505735047350373502735017350073472734717347073466734657346473463734627346173460734567345573454734537345273451734507344673445734447344373442734417344073436734357343473433734327343173430734267342573424734237342273421734207341673415734147341373412734117341073406734057340473403734027340173400733727337173370733667336573364733637336273361733607335673355733547335373352733517335073346733457334473343733427334173340733367333573334733337333273331733307332673325733247332373322733217332073316733157331473313733127331173310733067330573304733037330273301733007327273271732707326673265732647326373262732617326073256732557325473253732527325173250732467324573244732437324273241732407323673235732347323373232732317323073226732257322473223732227322173220732167321573214732137321273211732107320673205732047320373202732017320073172731717317073166731657316473163731627316173160731567315573154731537315273151731507314673145731447314373142731417314073136731357313473133731327313173130731267312573124731237312273121731207311673115731147311373112731117311073106731057310473103731027310173100730727307173070730667306573064730637306273061730607305673055730547305373052730517305073046730457304473043730427304173040730367303573034730337303273031730307302673025730247302373022730217302073016730157301473013730127301173010730067300573004730037300273001730007272672725727247272372722727217272072716727157271472713727127271172710727067270572704727037270272701727007267172670726667266572664726637266272661726607265672655726547265372652726517265072646726457264472643726427264172640726367263572634726337263272631726307262672625726247262372622726217262072616726157261472613726127261172610726067260572604726037260272601726007257172570725667256572564725637256272561725607255672555725547255372552725517255072546725457254472543725427254172540725367253572534725337253272531725307252672525725247252372522725217252072516725157251472513725127251172510725067250572504725037250272501725007247172470724667246572464724637246272461724607245672455724547245372452724517245072446724457244472443724427244172440724367243572434724337243272431724307242672425724247242372422724217242072416724157241472413724127241172410724067240572404724037240272401724007237172370723667236572364723637236272361723607235672355723547235372352723517235072346723457234472343723427234172340723367233572334723337233272331723307232672325723247232372322723217232072316723157231472313723127231172310723067230572304723037230272301723007227172270722667226572264722637226272261722607225672255722547225372252722517225072246722457224472243722427224172240722367223572234722337223272231722307222672225722247222372222722217222072216722157221472213722127221172210722067220572204722037220272201722007217172170721667216572164721637216272161721607215672155721547215372152721517215072146721457214472143721427214172140721367213572134721337213272131721307212672125721247212372122721217212072116721157211472113721127211172110721067210572104721037210272101721007207172070720667206572064720637206272061720607205672055720547205372052720517205072046720457204472043720427204172040720367203572034720337203272031720307202672025720247202372022720217202072016720157201472013720127201172010720067200572004720037200272001720007171671715717147171371712717117171071706717057170471703717027170171700716707166671665716647166371662716617166071656716557165471653716527165171650716467164571644716437164271641716407163671635716347163371632716317163071626716257162471623716227162171620716167161571614716137161271611716107160671605716047160371602716017160071570715667156571564715637156271561715607155671555715547155371552715517155071546715457154471543715427154171540715367153571534715337153271531715307152671525715247152371522715217152071516715157151471513715127151171510715067150571504715037150271501715007147071466714657146471463714627146171460714567145571454714537145271451714507144671445714447144371442714417144071436714357143471433714327143171430714267142571424714237142271421714207141671415714147141371412714117141071406714057140471403714027140171400713707136671365713647136371362713617136071356713557135471353713527135171350713467134571344713437134271341713407133671335713347133371332713317133071326713257132471323713227132171320713167131571314713137131271311713107130671305713047130371302713017130071270712667126571264712637126271261712607125671255712547125371252712517125071246712457124471243712427124171240712367123571234712337123271231712307122671225712247122371222712217122071216712157121471213712127121171210712067120571204712037120271201712007117071166711657116471163711627116171160711567115571154711537115271151711507114671145711447114371142711417114071136711357113471133711327113171130711267112571124711237112271121711207111671115711147111371112711117111071106711057110471103711027110171100710707106671065710647106371062710617106071056710557105471053710527105171050710467104571044710437104271041710407103671035710347103371032710317103071026710257102471023710227102171020710167101571014710137101271011710107100671005710047100371002710017100070706707057070470703707027070170700706667066570664706637066270661706607065670655706547065370652706517065070646706457064470643706427064170640706367063570634706337063270631706307062670625706247062370622706217062070616706157061470613706127061170610706067060570604706037060270601706007056670565705647056370562705617056070556705557055470553705527055170550705467054570544705437054270541705407053670535705347053370532705317053070526705257052470523705227052170520705167051570514705137051270511705107050670505705047050370502705017050070466704657046470463704627046170460704567045570454704537045270451704507044670445704447044370442704417044070436704357043470433704327043170430704267042570424704237042270421704207041670415704147041370412704117041070406704057040470403704027040170400703667036570364703637036270361703607035670355703547035370352703517035070346703457034470343703427034170340703367033570334703337033270331703307032670325703247032370322703217032070316703157031470313703127031170310703067030570304703037030270301703007026670265702647026370262702617026070256702557025470253702527025170250702467024570244702437024270241702407023670235702347023370232702317023070226702257022470223702227022170220702167021570214702137021270211702107020670205702047020370202702017020070166701657016470163701627016170160701567015570154701537015270151701507014670145701447014370142701417014070136701357013470133701327013170130701267012570124701237012270121701207011670115701147011370112701117011070106701057010470103701027010170100700667006570064700637006270061700607005670055700547005370052700517005070046700457004470043700427004170040700367003570034700337003270031700307002670025700247002370022700217002070016700157001470013700127001170010700067000570004700037000270001700006666656666466663666626666166660666556665466653666526665166650666456664466643666426664166640666356663466633666326663166630666256662466623666226662166620666156661466613666126661166610666056660466603666026660166600665656656466563665626656166560665556655466553665526655166550665456654466543665426654166540665356653466533665326653166530665256652466523665226652166520665156651466513665126651166510665056650466503665026650166500664656646466463664626646166460664556645466453664526645166450664456644466443664426644166440664356643466433664326643166430664256642466423664226642166420664156641466413664126641166410664056640466403664026640166400663656636466363663626636166360663556635466353663526635166350663456634466343663426634166340663356633466333663326633166330663256632466323663226632166320663156631466313663126631166310663056630466303663026630166300662656626466263662626626166260662556625466253662526625166250662456624466243662426624166240662356623466233662326623166230662256622466223662226622166220662156621466213662126621166210662056620466203662026620166200661656616466163661626616166160661556615466153661526615166150661456614466143661426614166140661356613466133661326613166130661256612466123661226612166120661156611466113661126611166110661056610466103661026610166100660656606466063660626606166060660556605466053660526605166050660456604466043660426604166040660356603466033660326603166030660256602466023660226602166020660156601466013660126601166010660056600466003660026600166000656556565465653656526565165650656456564465643656426564165640656356563465633656326563165630656256562465623656226562165620656156561465613656126561165610656056560465603656026560165600655646556365562655616556065555655546555365552655516555065545655446554365542655416554065535655346553365532655316553065525655246552365522655216552065515655146551365512655116551065505655046550365502655016550065464654636546265461654606545565454654536545265451654506544565444654436544265441654406543565434654336543265431654306542565424654236542265421654206541565414654136541265411654106540565404654036540265401654006536465363653626536165360653556535465353653526535165350653456534465343653426534165340653356533465333653326533165330653256532465323653226532165320653156531465313653126531165310653056530465303653026530165300652646526365262652616526065255652546525365252652516525065245652446524365242652416524065235652346523365232652316523065225652246522365222652216522065215652146521365212652116521065205652046520365202652016520065164651636516265161651606515565154651536515265151651506514565144651436514265141651406513565134651336513265131651306512565124651236512265121651206511565114651136511265111651106510565104651036510265101651006506465063650626506165060650556505465053650526505165050650456504465043650426504165040650356503465033650326503165030650256502465023650226502165020650156501465013650126501165010650056500465003650026500165000646456464464643646426464164640646356463464633646326463164630646256462464623646226462164620646156461464613646126461164610646056460464603646026460164600645636456264561645606455564554645536455264551645506454564544645436454264541645406453564534645336453264531645306452564524645236452264521645206451564514645136451264511645106450564504645036450264501645006446364462644616446064455644546445364452644516445064445644446444364442644416444064435644346443364432644316443064425644246442364422644216442064415644146441364412644116441064405644046440364402644016440064363643626436164360643556435464353643526435164350643456434464343643426434164340643356433464333643326433164330643256432464323643226432164320643156431464313643126431164310643056430464303643026430164300642636426264261642606425564254642536425264251642506424564244642436424264241642406423564234642336423264231642306422564224642236422264221642206421564214642136421264211642106420564204642036420264201642006416364162641616416064155641546415364152641516415064145641446414364142641416414064135641346413364132641316413064125641246412364122641216412064115641146411364112641116411064105641046410364102641016410064063640626406164060640556405464053640526405164050640456404464043640426404164040640356403464033640326403164030640256402464023640226402164020640156401464013640126401164010640056400464003640026400164000636356363463633636326363163630636256362463623636226362163620636156361463613636126361163610636056360463603636026360163600635626356163560635556355463553635526355163550635456354463543635426354163540635356353463533635326353163530635256352463523635226352163520635156351463513635126351163510635056350463503635026350163500634626346163460634556345463453634526345163450634456344463443634426344163440634356343463433634326343163430634256342463423634226342163420634156341463413634126341163410634056340463403634026340163400633626336163360633556335463353633526335163350633456334463343633426334163340633356333463333633326333163330633256332463323633226332163320633156331463313633126331163310633056330463303633026330163300632626326163260632556325463253632526325163250632456324463243632426324163240632356323463233632326323163230632256322463223632226322163220632156321463213632126321163210632056320463203632026320163200631626316163160631556315463153631526315163150631456314463143631426314163140631356313463133631326313163130631256312463123631226312163120631156311463113631126311163110631056310463103631026310163100630626306163060630556305463053630526305163050630456304463043630426304163040630356303463033630326303163030630256302463023630226302163020630156301463013630126301163010630056300463003630026300163000626256262462623626226262162620626156261462613626126261162610626056260462603626026260162600625616256062555625546255362552625516255062545625446254362542625416254062535625346253362532625316253062525625246252362522625216252062515625146251362512625116251062505625046250362502625016250062461624606245562454624536245262451624506244562444624436244262441624406243562434624336243262431624306242562424624236242262421624206241562414624136241262411624106240562404624036240262401624006236162360623556235462353623526235162350623456234462343623426234162340623356233462333623326233162330623256232462323623226232162320623156231462313623126231162310623056230462303623026230162300622616226062255622546225362252622516225062245622446224362242622416224062235622346223362232622316223062225622246222362222622216222062215622146221362212622116221062205622046220362202622016220062161621606215562154621536215262151621506214562144621436214262141621406213562134621336213262131621306212562124621236212262121621206211562114621136211262111621106210562104621036210262101621006206162060620556205462053620526205162050620456204462043620426204162040620356203462033620326203162030620256202462023620226202162020620156201462013620126201162010620056200462003620026200162000616156161461613616126161161610616056160461603616026160161600615606155561554615536155261551615506154561544615436154261541615406153561534615336153261531615306152561524615236152261521615206151561514615136151261511615106150561504615036150261501615006146061455614546145361452614516145061445614446144361442614416144061435614346143361432614316143061425614246142361422614216142061415614146141361412614116141061405614046140361402614016140061360613556135461353613526135161350613456134461343613426134161340613356133461333613326133161330613256132461323613226132161320613156131461313613126131161310613056130461303613026130161300612606125561254612536125261251612506124561244612436124261241612406123561234612336123261231612306122561224612236122261221612206121561214612136121261211612106120561204612036120261201612006116061155611546115361152611516115061145611446114361142611416114061135611346113361132611316113061125611246112361122611216112061115611146111361112611116111061105611046110361102611016110061060610556105461053610526105161050610456104461043610426104161040610356103461033610326103161030610256102461023610226102161020610156101461013610126101161010610056100461003610026100161000606056060460603606026060160600605556055460553605526055160550605456054460543605426054160540605356053460533605326053160530605256052460523605226052160520605156051460513605126051160510605056050460503605026050160500604556045460453604526045160450604456044460443604426044160440604356043460433604326043160430604256042460423604226042160420604156041460413604126041160410604056040460403604026040160400603556035460353603526035160350603456034460343603426034160340603356033460333603326033160330603256032460323603226032160320603156031460313603126031160310603056030460303603026030160300602556025460253602526025160250602456024460243602426024160240602356023460233602326023160230602256022460223602226022160220602156021460213602126021160210602056020460203602026020160200601556015460153601526015160150601456014460143601426014160140601356013460133601326013160130601256012460123601226012160120601156011460113601126011160110601056010460103601026010160100600556005460053600526005160050600456004460043600426004160040600356003460033600326003160030600256002460023600226002160020600156001460013600126001160010600056000460003600026000160000555554555535555255551555505554455543555425554155540555345553355532555315553055524555235552255521555205551455513555125551155510555045550355502555015550055454554535545255451554505544455443554425544155440554345543355432554315543055424554235542255421554205541455413554125541155410554045540355402554015540055354553535535255351553505534455343553425534155340553345533355332553315533055324553235532255321553205531455313553125531155310553045530355302553015530055254552535525255251552505524455243552425524155240552345523355232552315523055224552235522255221552205521455213552125521155210552045520355202552015520055154551535515255151551505514455143551425514155140551345513355132551315513055124551235512255121551205511455113551125511155110551045510355102551015510055054550535505255051550505504455043550425504155040550345503355032550315503055024550235502255021550205501455013550125501155010550045500355002550015500054544545435454254541545405453454533545325453154530545245452354522545215452054514545135451254511545105450454503545025450154500544535445254451544505444454443544425444154440544345443354432544315443054424544235442254421544205441454413544125441154410544045440354402544015440054353543525435154350543445434354342543415434054334543335433254331543305432454323543225432154320543145431354312543115431054304543035430254301543005425354252542515425054244542435424254241542405423454233542325423154230542245422354222542215422054214542135421254211542105420454203542025420154200541535415254151541505414454143541425414154140541345413354132541315413054124541235412254121541205411454113541125411154110541045410354102541015410054053540525405154050540445404354042540415404054034540335403254031540305402454023540225402154020540145401354012540115401054004540035400254001540005353453533535325353153530535245352353522535215352053514535135351253511535105350453503535025350153500534525345153450534445344353442534415344053434534335343253431534305342453423534225342153420534145341353412534115341053404534035340253401534005335253351533505334453343533425334153340533345333353332533315333053324533235332253321533205331453313533125331153310533045330353302533015330053252532515325053244532435324253241532405323453233532325323153230532245322353222532215322053214532135321253211532105320453203532025320153200531525315153150531445314353142531415314053134531335313253131531305312453123531225312153120531145311353112531115311053104531035310253101531005305253051530505304453043530425304153040530345303353032530315303053024530235302253021530205301453013530125301153010530045300353002530015300052524525235252252521525205251452513525125251152510525045250352502525015250052451524505244452443524425244152440524345243352432524315243052424524235242252421524205241452413524125241152410524045240352402524015240052351523505234452343523425234152340523345233352332523315233052324523235232252321523205231452313523125231152310523045230352302523015230052251522505224452243522425224152240522345223352232522315223052224522235222252221522205221452213522125221152210522045220352202522015220052151521505214452143521425214152140521345213352132521315213052124521235212252121521205211452113521125211152110521045210352102521015210052051520505204452043520425204152040520345203352032520315203052024520235202252021520205201452013520125201152010520045200352002520015200051514515135151251511515105150451503515025150151500514505144451443514425144151440514345143351432514315143051424514235142251421514205141451413514125141151410514045140351402514015140051350513445134351342513415134051334513335133251331513305132451323513225132151320513145131351312513115131051304513035130251301513005125051244512435124251241512405123451233512325123151230512245122351222512215122051214512135121251211512105120451203512025120151200511505114451143511425114151140511345113351132511315113051124511235112251121511205111451113511125111151110511045110351102511015110051050510445104351042510415104051034510335103251031510305102451023510225102151020510145101351012510115101051004510035100251001510005050450503505025050150500504445044350442504415044050434504335043250431504305042450423504225042150420504145041350412504115041050404504035040250401504005034450343503425034150340503345033350332503315033050324503235032250321503205031450313503125031150310503045030350302503015030050244502435024250241502405023450233502325023150230502245022350222502215022050214502135021250211502105020450203502025020150200501445014350142501415014050134501335013250131501305012450123501225012150120501145011350112501115011050104501035010250101501005004450043500425004150040500345003350032500315003050024500235002250021500205001450013500125001150010500045000350002500015000044444344442444414444044433444324443144430444234442244421444204441344412444114441044403444024440144400443434434244341443404433344332443314433044323443224432144320443134431244311443104430344302443014430044243442424424144240442334423244231442304422344222442214422044213442124421144210442034420244201442004414344142441414414044133441324413144130441234412244121441204411344112441114411044103441024410144100440434404244041440404403344032440314403044023440224402144020440134401244011440104400344002440014400043433434324343143430434234342243421434204341343412434114341043403434024340143400433424334143340433334333243331433304332343322433214332043313433124331143310433034330243301433004324243241432404323343232432314323043223432224322143220432134321243211432104320343202432014320043142431414314043133431324313143130431234312243121431204311343112431114311043103431024310143100430424304143040430334303243031430304302343022430214302043013430124301143010430034300243001430004242342422424214242042413424124241142410424034240242401424004234142340423334233242331423304232342322423214232042313423124231142310423034230242301423004224142240422334223242231422304222342222422214222042213422124221142210422034220242201422004214142140421334213242131421304212342122421214212042113421124211142110421034210242101421004204142040420334203242031420304202342022420214202042013420124201142010420034200242001420004141341412414114141041403414024140141400413404133341332413314133041323413224132141320413134131241311413104130341302413014130041240412334123241231412304122341222412214122041213412124121141210412034120241201412004114041133411324113141130411234112241121411204111341112411114111041103411024110141100410404103341032410314103041023410224102141020410134101241011410104100341002410014100040403404024040140400403334033240331403304032340322403214032040313403124031140310403034030240301403004023340232402314023040223402224022140220402134021240211402104020340202402014020040133401324013140130401234012240121401204011340112401114011040103401024010140100400334003240031400304002340022400214002040013400124001140010400034000240001400003333323333133330333223332133320333123331133310333023330133300332323323133230332223322133220332123321133210332023320133200331323313133130331223312133120331123311133110331023310133100330323303133030330223302133020330123301133010330023300133000323223232132320323123231132310323023230132300322313223032222322213222032212322113221032202322013220032131321303212232121321203211232111321103210232101321003203132030320223202132020320123201132010320023200132000313123131131310313023130131300312303122231221312203121231211312103120231201312003113031122311213112031112311113111031102311013110031030310223102131020310123101131010310023100131000303023030130300302223022130220302123021130210302023020130200301223012130120301123011130110301023010130100300223002130020300123001130010300023000130000222221222202221122210222012220022121221202211122110221012210022021220202201122010220012200021211212102120121200211202111121110211012110021020210112101021001210002020120200201112011020101201002001120010200012000011111011100110101100010100100000

Comment hidden because of low score. Click to expand.
0
of 0 vote

Had a go with this with multidimensional Array.
Shabby wrk, but the logic seems to work.

Here goes the pseudocode:

press 0's till lenght-1;
have a note of the last (length-1) digits pressed.
find a number when pressed will generate the largest key that was not pressed before.
update last digits pressed with the new number pressed.
stop when all keys are pressed.

The worst case scenario is (largest value + length)
So if length is 4 worst case is (9999 + 4) = 10003
if length is 4 worstcase is (99999 + 5) = 100004

Comment hidden because of low score. Click to expand.
0
of 0 vote

The above code will be one of the best efficient ways to generate as every number you press will check for a new key.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The key string for a length of 3 is givven below

``009998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101000``

Comment hidden because of low score. Click to expand.
0
of 0 vote

b=passcode;
pressKey:
start;
store a=0;
loop1:
input num;
a = (a*10) + num;
while a.length != b.length goto loop1;
store c = checkNum(num);
if k is true
print "Succeed";
reset a;
else
goto loop1;

checkNum(num):
val = Math.power(10,b.length);
num = num % val;
if num == b
return true;
else
return false;

Comment hidden because of low score. Click to expand.
0
of 0 vote

b=passcode;
pressKey:
start;
store a=0;
loop1:
input num;
a = (a*10) + num;
while a.length != b.length goto loop1;
store c = checkNum(num);
if k is true
print "Succeed";
reset a;
else
goto loop1;

checkNum(num):
val = Math.power(10,b.length);
num = num % val;
if num == b
return true;
else
return false;

Comment hidden because of low score. Click to expand.
0
of 0 vote

since we dont know the valid sequence in advance, KMP is not an option.

If the length of sequence 'P' is known is known, we just keep track of last 'P' chars and just print it out when the key is accpeted.

if the length of key is not known we have no option but to walk backwards whenever the key is accepted and find the key.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I would build a circular queue with a size (5 max size of the password). Once the queue is full, collect the elements and validate against the correct password. If the password does not match return error and reset the queue. this way user can enter next set of password.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Polynomial hashing, rolling hash (kinda like Rabin-Karp string matching algorithm) should do the trick for (i).

Comment hidden because of low score. Click to expand.
0

That ends up being worse than brute force though...

Comment hidden because of low score. Click to expand.
0

What? Rabin-Karp works in expected linear time. Check out a reference.

Comment hidden because of low score. Click to expand.
0

What? How?
Rabin-Karp works in expected linear time. Refer to a standard text.
Rolling hash calculation for window (i+1 to j+1) can be calculated from the hash for window (i to j) in constant time. Use of a proper base for polynomial hashing will greatly reduce false positives.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.