Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
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;
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++){
lastNum.add(0);
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);
multiArray.add(false);
lastNum.remove(0);
lastNum.add(i);
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++){
pList.add(true);
}
}
else if(length > 1){
for (int i=0;i<10;i++){
ArrayList<Object> temp = new ArrayList<>();
pList.add(initArray(length-1, temp));
}
}
return pList;
}
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 ???
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.
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 ???
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
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?
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);
while (! KeyPad.pressKey(key)
&& 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
&& KeyPad.pressKey(key))
return key ; // found the key
else
return findKey(entered + 1);
}
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);
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...
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
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
I think that for this problem, the goal is to press the least number of keys, rather than find the combination more efficiently.
I tried it with linked list , please have a look and improve me :)
public class LinkedList {
int data;
LinkedList next;
public LinkedList()
{
this.data=0;
this.next=null;
}
public LinkedList(int data)
{
this.data=data;
this.next=null;
}
public static LinkedList Insert(LinkedList root,int data)
{
if(root==null)
{
root.data=data;
return root;
}
else
{
LinkedList newnode=new LinkedList();
newnode.data=data;
newnode.next=root;
return newnode;
}
}
public static void deleteLast(LinkedList root)
{
if(root==null)
return;
else
{
LinkedList prev = null;
while(root.next!=null)
{
prev=root;
root=root.next;
}
prev.next=null;
}
}
public static void printlinkedList(LinkedList root)
{
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;
LinkedList root=new LinkedList(Integer.parseInt(seq.charAt(0)+""));
while(count!=(len-1))
{
count++;
data=Integer.parseInt(seq.charAt(j)+"");
j++;
root=LinkedList.Insert(root, data);
if(count>=(arr.length-1))
{
flag=CheckSequence(root,arr);
if(flag==true)
break;
LinkedList.deleteLast(root);
}
}
if(flag==true)
{
System.out.println("Acess Granted");
}
else
{
System.out.println("Wrong Password");
}
// LinkedList.printlinkedList(root);
}
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;
}
}
import java.util.Scanner;
public class PasswordCheck {
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;
}
}
private node head= null;
private void addnode(int d)
{
node nd = new node(d);
if(head == null)
{
head = nd;
}
else
{
nd.next = head;
head = nd;
}
length++;
}
private void delete(){
node cur = head;
node prev = null;
while(cur.next!= null)
{
prev = cur;
cur= cur.next;
}
prev.next = null;
length--;
}
private int listSize()
{
return length;
}
private StringBuilder stringBuild()
{
node temp = head;
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");
PasswordCheck ps = new PasswordCheck();
int key;
String password = "12345";
Scanner sc = new Scanner(System.in);
while((key = sc.nextInt())!= -1)
{
ps.addnode(key);
if(ps.listSize() == 5)
{
// Check if the keys are correct
// Build the string
if(String.valueOf(ps.stringBuild()).contentEquals(password))
{
System.out.println("Unlocked");
System.exit(0);
}
ps.delete();
}
}
}
}
import java.util.Scanner;
public class PasswordCheck {
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;
}
}
private node head= null;
private void addnode(int d)
{
node nd = new node(d);
if(head == null)
{
head = nd;
}
else
{
nd.next = head;
head = nd;
}
length++;
}
private void delete(){
node cur = head;
node prev = null;
while(cur.next!= null)
{
prev = cur;
cur= cur.next;
}
prev.next = null;
length--;
}
private int listSize()
{
return length;
}
private StringBuilder stringBuild()
{
node temp = head;
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");
PasswordCheck ps = new PasswordCheck();
int key;
String password = "12345";
Scanner sc = new Scanner(System.in);
while((key = sc.nextInt())!= -1)
{
ps.addnode(key);
if(ps.listSize() == 5)
{
// Check if the keys are correct
// Build the string
if(String.valueOf(ps.stringBuild()).contentEquals(password))
{
System.out.println("Unlocked");
System.exit(0);
}
ps.delete();
}
}
}
}
import java.util.Scanner;
public class PasswordCheck {
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;
}
}
private node head= null;
private void addnode(int d)
{
node nd = new node(d);
if(head == null)
{
head = nd;
}
else
{
nd.next = head;
head = nd;
}
length++;
}
private void delete(){
node cur = head;
node prev = null;
while(cur.next!= null)
{
prev = cur;
cur= cur.next;
}
prev.next = null;
length--;
}
private int listSize()
{
return length;
}
private StringBuilder stringBuild()
{
node temp = head;
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");
PasswordCheck ps = new PasswordCheck();
int key;
String password = "12345";
Scanner sc = new Scanner(System.in);
while((key = sc.nextInt())!= -1)
{
ps.addnode(key);
if(ps.listSize() == 5)
{
// Check if the keys are correct
// Build the string
if(String.valueOf(ps.stringBuild()).contentEquals(password))
{
System.out.println("Unlocked");
System.exit(0);
}
ps.delete();
}
}
}
}
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;
}
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)
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)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace RandomPuzzles
{
class LockerKey
{
private static string key = "98345";
private static string sequence;
private static int numKeysEntered;
private static int numComparisonsMade;
private static Dictionary<string, bool> elapsedSet = new Dictionary<string, bool>();
public static string Solve()
{
sequence = "00000";
elapsedSet.Add(sequence, true);
while (numComparisonsMade < 100000)
{
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);
Console.WriteLine("Match Found: {0}, NumKeyPresses: {1}, NumComparisonsMade: {2}", finalKey, numKeysEntered, numComparisonsMade);
return finalKey;
}
break;
}
}
}
return null;
}
private static bool IsKey()
{
numComparisonsMade++;
var start = sequence.Length - 5;
var newKey = sequence.Substring(start, 5);
elapsedSet.Add(newKey, true);
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++)
{
appendedString = i.ToString().PadLeft(length, '0');
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;
}
}
}
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);
}
}
}
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).
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.Write("Enter Password");
string pwd = Console.ReadLine();
Console.WriteLine("Enter Sequence");
string inputSequence = Console.ReadLine();
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;
}
public bool FindMatch()
{
Console.Write("Enter Password");
string pwd = Console.ReadLine();
Console.WriteLine("Enter Sequence");
string inputSequence = Console.ReadLine();
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;
}
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;
}
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;
}
00009999989999799996999959999499993999929999199990999889998799986999859998499983999829998199980999789997799976999759997499973999729997199970999689996799966999659996499963999629996199960999589995799956999559995499953999529995199950999489994799946999459994499943999429994199940999389993799936999359993499933999329993199930999289992799926999259992499923999229992199920999189991799916999159991499913999129991199910999089990799906999059990499903999029990199900998989989799896998959989499893998929989199890998889988799886998859988499883998829988199880998789987799876998759987499873998729987199870998689986799866998659986499863998629986199860998589985799856998559985499853998529985199850998489984799846998459984499843998429984199840998389983799836998359983499833998329983199830998289982799826998259982499823998229982199820998189981799816998159981499813998129981199810998089980799806998059980499803998029980199800997989979799796997959979499793997929979199790997889978799786997859978499783997829978199780997789977799776997759977499773997729977199770997689976799766997659976499763997629976199760997589975799756997559975499753997529975199750997489974799746997459974499743997429974199740997389973799736997359973499733997329973199730997289972799726997259972499723997229972199720997189971799716997159971499713997129971199710997089970799706997059970499703997029970199700996989969799696996959969499693996929969199690996889968799686996859968499683996829968199680996789967799676996759967499673996729967199670996689966799666996659966499663996629966199660996589965799656996559965499653996529965199650996489964799646996459964499643996429964199640996389963799636996359963499633996329963199630996289962799626996259962499623996229962199620996189961799616996159961499613996129961199610996089960799606996059960499603996029960199600995989959799596995959959499593995929959199590995889958799586995859958499583995829958199580995789957799576995759957499573995729957199570995689956799566995659956499563995629956199560995589955799556995559955499553995529955199550995489954799546995459954499543995429954199540995389953799536995359953499533995329953199530995289952799526995259952499523995229952199520995189951799516995159951499513995129951199510995089950799506995059950499503995029950199500994989949799496994959949499493994929949199490994889948799486994859948499483994829948199480994789947799476994759947499473994729947199470994689946799466994659946499463994629946199460994589945799456994559945499453994529945199450994489944799446994459944499443994429944199440994389943799436994359943499433994329943199430994289942799426994259942499423994229942199420994189941799416994159941499413994129941199410994089940799406994059940499403994029940199400993989939799396993959939499393993929939199390993889938799386993859938499383993829938199380993789937799376993759937499373993729937199370993689936799366993659936499363993629936199360993589935799356993559935499353993529935199350993489934799346993459934499343993429934199340993389933799336993359933499333993329933199330993289932799326993259932499323993229932199320993189931799316993159931499313993129931199310993089930799306993059930499303993029930199300992989929799296992959929499293992929929199290992889928799286992859928499283992829928199280992789927799276992759927499273992729927199270992689926799266992659926499263992629926199260992589925799256992559925499253992529925199250992489924799246992459924499243992429924199240992389923799236992359923499233992329923199230992289922799226992259922499223992229922199220992189921799216992159921499213992129921199210992089920799206992059920499203992029920199200991989919799196991959919499193991929919199190991889918799186991859918499183991829918199180991789917799176991759917499173991729917199170991689916799166991659916499163991629916199160991589915799156991559915499153991529915199150991489914799146991459914499143991429914199140991389913799136991359913499133991329913199130991289912799126991259912499123991229912199120991189911799116991159911499113991129911199110991089910799106991059910499103991029910199100990989909799096990959909499093990929909199090990889908799086990859908499083990829908199080990789907799076990759907499073990729907199070990689906799066990659906499063990629906199060990589905799056990559905499053990529905199050990489904799046990459904499043990429904199040990389903799036990359903499033990329903199030990289902799026990259902499023990229902199020990189901799016990159901499013990129901199010990089900799006990059900499003990029900199000989889898798986989859898498983989829898198980989789897798976989759897498973989729897198970989689896798966989659896498963989629896198960989589895798956989559895498953989529895198950989489894798946989459894498943989429894198940989389893798936989359893498933989329893198930989289892798926989259892498923989229892198920989189891798916989159891498913989129891198910989089890798906989059890498903989029890198900988979889698895988949889398892988919889098888988879888698885988849888398882988819888098878988779887698875988749887398872988719887098868988679886698865988649886398862988619886098858988579885698855988549885398852988519885098848988479884698845988449884398842988419884098838988379883698835988349883398832988319883098828988279882698825988249882398822988219882098818988179881698815988149881398812988119881098808988079880698805988049880398802988019880098797987969879598794987939879298791987909878898787987869878598784987839878298781987809877898777987769877598774987739877298771987709876898767987669876598764987639876298761987609875898757987569875598754987539875298751987509874898747987469874598744987439874298741987409873898737987369873598734987339873298731987309872898727987269872598724987239872298721987209871898717987169871598714987139871298711987109870898707987069870598704987039870298701987009869798696986959869498693986929869198690986889868798686986859868498683986829868198680986789867798676986759867498673986729867198670986689866798666986659866498663986629866198660986589865798656986559865498653986529865198650986489864798646986459864498643986429864198640986389863798636986359863498633986329863198630986289862798626986259862498623986229862198620986189861798616986159861498613986129861198610986089860798606986059860498603986029860198600985979859698595985949859398592985919859098588985879858698585985849858398582985819858098578985779857698575985749857398572985719857098568985679856698565985649856398562985619856098558985579855698555985549855398552985519855098548985479854698545985449854398542985419854098538985379853698535985349853398532985319853098528985279852698525985249852398522985219852098518985179851698515985149851398512985119851098508985079850698505985049850398502985019850098497984969849598494984939849298491984909848898487984869848598484984839848298481984809847898477984769847598474984739847298471984709846898467984669846598464984639846298461984609845898457984569845598454984539845298451984509844898447984469844598444984439844298441984409843898437984369843598434984339843298431984309842898427984269842598424984239842298421984209841898417984169841598414984139841298411984109840898407984069840598404984039840298401984009839798396983959839498393983929839198390983889838798386983859838498383983829838198380983789837798376983759837498373983729837198370983689836798366983659836498363983629836198360983589835798356983559835498353983529835198350983489834798346983459834498343983429834198340983389833798336983359833498333983329833198330983289832798326983259832498323983229832198320983189831798316983159831498313983129831198310983089830798306983059830498303983029830198300982979829698295982949829398292982919829098288982879828698285982849828398282982819828098278982779827698275982749827398272982719827098268982679826698265982649826398262982619826098258982579825698255982549825398252982519825098248982479824698245982449824398242982419824098238982379823698235982349823398232982319823098228982279822698225982249822398222982219822098218982179821698215982149821398212982119821098208982079820698205982049820398202982019820098197981969819598194981939819298191981909818898187981869818598184981839818298181981809817898177981769817598174981739817298171981709816898167981669816598164981639816298161981609815898157981569815598154981539815298151981509814898147981469814598144981439814298141981409813898137981369813598134981339813298131981309812898127981269812598124981239812298121981209811898117981169811598114981139811298111981109810898107981069810598104981039810298101981009809798096980959809498093980929809198090980889808798086980859808498083980829808198080980789807798076980759807498073980729807198070980689806798066980659806498063980629806198060980589805798056980559805498053980529805198050980489804798046980459804498043980429804198040980389803798036980359803498033980329803198030980289802798026980259802498023980229802198020980189801798016980159801498013980129801198010980089800798006980059800498003980029800198000979789797797976979759797497973979729797197970979689796797966979659796497963979629796197960979589795797956979559795497953979529795197950979489794797946979459794497943979429794197940979389793797936979359793497933979329793197930979289792797926979259792497923979229792197920979189791797916979159791497913979129791197910979089790797906979059790497903979029790197900978969789597894978939789297891978909788897887978869788597884978839788297881978809787897877978769787597874978739787297871978709786897867978669786597864978639786297861978609785897857978569785597854978539785297851978509784897847978469784597844978439784297841978409783897837978369783597834978339783297831978309782897827978269782597824978239782297821978209781897817978169781597814978139781297811978109780897807978069780597804978039780297801978009779697795977949779397792977919779097788977879778697785977849778397782977819778097778977779777697775977749777397772977719777097768977679776697765977649776397762977619776097758977579775697755977549775397752977519775097748977479774697745977449774397742977419774097738977379773697735977349773397732977319773097728977279772697725977249772397722977219772097718977179771697715977149771397712977119771097708977079770697705977049770397702977019770097696976959769497693976929769197690976889768797686976859768497683976829768197680976789767797676976759767497673976729767197670976689766797666976659766497663976629766197660976589765797656976559765497653976529765197650976489764797646976459764497643976429764197640976389763797636976359763497633976329763197630976289762797626976259762497623976229762197620976189761797616976159761497613976129761197610976089760797606976059760497603976029760197600975969759597594975939759297591975909758897587975869758597584975839758297581975809757897577975769757597574975739757297571975709756897567975669756597564975639756297561975609755897557975569755597554975539755297551975509754897547975469754597544975439754297541975409753897537975369753597534975339753297531975309752897527975269752597524975239752297521975209751897517975169751597514975139751297511975109750897507975069750597504975039750297501975009749697495974949749397492974919749097488974879748697485974849748397482974819748097478974779747697475974749747397472974719747097468974679746697465974649746397462974619746097458974579745697455974549745397452974519745097448974479744697445974449744397442974419744097438974379743697435974349743397432974319743097428974279742697425974249742397422974219742097418974179741697415974149741397412974119741097408974079740697405974049740397402974019740097396973959739497393973929739197390973889738797386973859738497383973829738197380973789737797376973759737497373973729737197370973689736797366973659736497363973629736197360973589735797356973559735497353973529735197350973489734797346973459734497343973429734197340973389733797336973359733497333973329733197330973289732797326973259732497323973229732197320973189731797316973159731497313973129731197310973089730797306973059730497303973029730197300972969729597294972939729297291972909728897287972869728597284972839728297281972809727897277972769727597274972739727297271972709726897267972669726597264972639726297261972609725897257972569725597254972539725297251972509724897247972469724597244972439724297241972409723897237972369723597234972339723297231972309722897227972269722597224972239722297221972209721897217972169721597214972139721297211972109720897207972069720597204972039720297201972009719697195971949719397192971919719097188971879718697185971849718397182971819718097178971779717697175971749717397172971719717097168971679716697165971649716397162971619716097158971579715697155971549715397152971519715097148971479714697145971449714397142971419714097138971379713697135971349713397132971319713097128971279712697125971249712397122971219712097118971179711697115971149711397112971119711097108971079710697105971049710397102971019710097096970959709497093970929709197090970889708797086970859708497083970829708197080970789707797076970759707497073970729707197070970689706797066970659706497063970629706197060970589705797056970559705497053970529705197050970489704797046970459704497043970429704197040970389703797036970359703497033970329703197030970289702797026970259702497023970229702197020970189701797016970159701497013970129701197010970089700797006970059700497003970029700197000969689696796966969659696496963969629696196960969589695796956969559695496953969529695196950969489694796946969459694496943969429694196940969389693796936969359693496933969329693196930969289692796926969259692496923969229692196920969189691796916969159691496913969129691196910969089690796906969059690496903969029690196900968959689496893968929689196890968889688796886968859688496883968829688196880968789687796876968759687496873968729687196870968689686796866968659686496863968629686196860968589685796856968559685496853968529685196850968489684796846968459684496843968429684196840968389683796836968359683496833968329683196830968289682796826968259682496823968229682196820968189681796816968159681496813968129681196810968089680796806968059680496803968029680196800967959679496793967929679196790967889678796786967859678496783967829678196780967789677796776967759677496773967729677196770967689676796766967659676496763967629676196760967589675796756967559675496753967529675196750967489674796746967459674496743967429674196740967389673796736967359673496733967329673196730967289672796726967259672496723967229672196720967189671796716967159671496713967129671196710967089670796706967059670496703967029670196700966959669496693966929669196690966889668796686966859668496683966829668196680966789667796676966759667496673966729667196670966689666796666966659666496663966629666196660966589665796656966559665496653966529665196650966489664796646966459664496643966429664196640966389663796636966359663496633966329663196630966289662796626966259662496623966229662196620966189661796616966159661496613966129661196610966089660796606966059660496603966029660196600965959659496593965929659196590965889658796586965859658496583965829658196580965789657796576965759657496573965729657196570965689656796566965659656496563965629656196560965589655796556965559655496553965529655196550965489654796546965459654496543965429654196540965389653796536965359653496533965329653196530965289652796526965259652496523965229652196520965189651796516965159651496513965129651196510965089650796506965059650496503965029650196500964959649496493964929649196490964889648796486964859648496483964829648196480964789647796476964759647496473964729647196470964689646796466964659646496463964629646196460964589645796456964559645496453964529645196450964489644796446964459644496443964429644196440964389643796436964359643496433964329643196430964289642796426964259642496423964229642196420964189641796416964159641496413964129641196410964089640796406964059640496403964029640196400963959639496393963929639196390963889638796386963859638496383963829638196380963789637796376963759637496373963729637196370963689636796366963659636496363963629636196360963589635796356963559635496353963529635196350963489634796346963459634496343963429634196340963389633796336963359633496333963329633196330963289632796326963259632496323963229632196320963189631796316963159631496313963129631196310963089630796306963059630496303963029630196300962959629496293962929629196290962889628796286962859628496283962829628196280962789627796276962759627496273962729627196270962689626796266962659626496263962629626196260962589625796256962559625496253962529625196250962489624796246962459624496243962429624196240962389623796236962359623496233962329623196230962289622796226962259622496223962229622196220962189621796216962159621496213962129621196210962089620796206962059620496203962029620196200961959619496193961929619196190961889618796186961859618496183961829618196180961789617796176961759617496173961729617196170961689616796166961659616496163961629616196160961589615796156961559615496153961529615196150961489614796146961459614496143961429614196140961389613796136961359613496133961329613196130961289612796126961259612496123961229612196120961189611796116961159611496113961129611196110961089610796106961059610496103961029610196100960959609496093960929609196090960889608796086960859608496083960829608196080960789607796076960759607496073960729607196070960689606796066960659606496063960629606196060960589605796056960559605496053960529605196050960489604796046960459604496043960429604196040960389603796036960359603496033960329603196030960289602796026960259602496023960229602196020960189601796016960159601496013960129601196010960089600796006960059600496003960029600196000959589595795956959559595495953959529595195950959489594795946959459594495943959429594195940959389593795936959359593495933959329593195930959289592795926959259592495923959229592195920959189591795916959159591495913959129591195910959089590795906959059590495903959029590195900958949589395892958919589095888958879588695885958849588395882958819588095878958779587695875958749587395872958719587095868958679586695865958649586395862958619586095858958579585695855958549585395852958519585095848958479584695845958449584395842958419584095838958379583695835958349583395832958319583095828958279582695825958249582395822958219582095818958179581695815958149581395812958119581095808958079580695805958049580395802958019580095794957939579295791957909578895787957869578595784957839578295781957809577895777957769577595774957739577295771957709576895767957669576595764957639576295761957609575895757957569575595754957539575295751957509574895747957469574595744957439574295741957409573895737957369573595734957339573295731957309572895727957269572595724957239572295721957209571895717957169571595714957139571295711957109570895707957069570595704957039570295701957009569495693956929569195690956889568795686956859568495683956829568195680956789567795676956759567495673956729567195670956689566795666956659566495663956629566195660956589565795656956559565495653956529565195650956489564795646956459564495643956429564195640956389563795636956359563495633956329563195630956289562795626956259562495623956229562195620956189561795616956159561495613956129561195610956089560795606956059560495603956029560195600955949559395592955919559095588955879558695585955849558395582955819558095578955779557695575955749557395572955719557095568955679556695565955649556395562955619556095558955579555695555955549555395552955519555095548955479554695545955449554395542955419554095538955379553695535955349553395532955319553095528955279552695525955249552395522955219552095518955179551695515955149551395512955119551095508955079550695505955049550395502955019550095494954939549295491954909548895487954869548595484954839548295481954809547895477954769547595474954739547295471954709546895467954669546595464954639546295461954609545895457954569545595454954539545295451954509544895447954469544595444954439544295441954409543895437954369543595434954339543295431954309542895427954269542595424954239542295421954209541895417954169541595414954139541295411954109540895407954069540595404954039540295401954009539495393953929539195390953889538795386953859538495383953829538195380953789537795376953759537495373953729537195370953689536795366953659536495363953629536195360953589535795356953559535495353953529535195350953489534795346953459534495343953429534195340953389533795336953359533495333953329533195330953289532795326953259532495323953229532195320953189531795316953159531495313953129531195310953089530795306953059530495303953029530195300952949529395292952919529095288952879528695285952849528395282952819528095278952779527695275952749527395272952719527095268952679526695265952649526395262952619526095258952579525695255952549525395252952519525095248952479524695245952449524395242952419524095238952379523695235952349523395232952319523095228952279522695225952249522395222952219522095218952179521695215952149521395212952119521095208952079520695205952049520395202952019520095194951939519295191951909518895187951869518595184951839518295181951809517895177951769517595174951739517295171951709516895167951669516595164951639516295161951609515895157951569515595154951539515295151951509514895147951469514595144951439514295141951409513895137951369513595134951339513295131951309512895127951269512595124951239512295121951209511895117951169511595114951139511295111951109510895107951069510595104951039510295101951009509495093950929509195090950889508795086950859508495083950829508195080950789507795076950759507495073950729507195070950689506795066950659506495063950629506195060950589505795056950559505495053950529505195050950489504795046950459504495043950429504195040950389503795036950359503495033950329503195030950289502795026950259502495023950229502195020950189501795016950159501495013950129501195010950089500795006950059500495003950029500195000949489494794946949459494494943949429494194940949389493794936949359493494933949329493194930949289492794926949259492494923949229492194920949189491794916949159491494913949129491194910949089490794906949059490494903949029490194900948939489294891948909488894887948869488594884948839488294881948809487894877948769487594874948739487294871948709486894867948669486594864948639486294861948609485894857948569485594854948539485294851948509484894847948469484594844948439484294841948409483894837948369483594834948339483294831948309482894827948269482594824948239482294821948209481894817948169481594814948139481294811948109480894807948069480594804948039480294801948009479394792947919479094788947879478694785947849478394782947819478094778947779477694775947749477394772947719477094768947679476694765947649476394762947619476094758947579475694755947549475394752947519475094748947479474694745947449474394742947419474094738947379473694735947349473394732947319473094728947279472694725947249472394722947219472094718947179471694715947149471394712947119471094708947079470694705947049470394702947019470094693946929469194690946889468794686946859468494683946829468194680946789467794676946759467494673946729467194670946689466794666946659466494663946629466194660946589465794656946559465494653946529465194650946489464794646946459464494643946429464194640946389463794636946359463494633946329463194630946289462794626946259462494623946229462194620946189461794616946159461494613946129461194610946089460794606946059460494603946029460194600945939459294591945909458894587945869458594584945839458294581945809457894577945769457594574945739457294571945709456894567945669456594564945639456294561945609455894557945569455594554945539455294551945509454894547945469454594544945439454294541945409453894537945369453594534945339453294531945309452894527945269452594524945239452294521945209451894517945169451594514945139451294511945109450894507945069450594504945039450294501945009449394492944919449094488944879448694485944849448394482944819448094478944779447694475944749447394472944719447094468944679446694465944649446394462944619446094458944579445694455944549445394452944519445094448944479444694445944449444394442944419444094438944379443694435944349443394432944319443094428944279442694425944249442394422944219442094418944179441694415944149441394412944119441094408944079440694405944049440394402944019440094393943929439194390943889438794386943859438494383943829438194380943789437794376943759437494373943729437194370943689436794366943659436494363943629436194360943589435794356943559435494353943529435194350943489434794346943459434494343943429434194340943389433794336943359433494333943329433194330943289432794326943259432494323943229432194320943189431794316943159431494313943129431194310943089430794306943059430494303943029430194300942939429294291942909428894287942869428594284942839428294281942809427894277942769427594274942739427294271942709426894267942669426594264942639426294261942609425894257942569425594254942539425294251942509424894247942469424594244942439424294241942409423894237942369423594234942339423294231942309422894227942269422594224942239422294221942209421894217942169421594214942139421294211942109420894207942069420594204942039420294201942009419394192941919419094188941879418694185941849418394182941819418094178941779417694175941749417394172941719417094168941679416694165941649416394162941619416094158941579415694155941549415394152941519415094148941479414694145941449414394142941419414094138941379413694135941349413394132941319413094128941279412694125941249412394122941219412094118941179411694115941149411394112941119411094108941079410694105941049410394102941019410094093940929409194090940889408794086940859408494083940829408194080940789407794076940759407494073940729407194070940689406794066940659406494063940629406194060940589405794056940559405494053940529405194050940489404794046940459404494043940429404194040940389403794036940359403494033940329403194030940289402794026940259402494023940229402194020940189401794016940159401494013940129401194010940089400794006940059400494003940029400194000939389393793936939359393493933939329393193930939289392793926939259392493923939229392193920939189391793916939159391493913939129391193910939089390793906939059390493903939029390193900938929389193890938889388793886938859388493883938829388193880938789387793876938759387493873938729387193870938689386793866938659386493863938629386193860938589385793856938559385493853938529385193850938489384793846938459384493843938429384193840938389383793836938359383493833938329383193830938289382793826938259382493823938229382193820938189381793816938159381493813938129381193810938089380793806938059380493803938029380193800937929379193790937889378793786937859378493783937829378193780937789377793776937759377493773937729377193770937689376793766937659376493763937629376193760937589375793756937559375493753937529375193750937489374793746937459374493743937429374193740937389373793736937359373493733937329373193730937289372793726937259372493723937229372193720937189371793716937159371493713937129371193710937089370793706937059370493703937029370193700936929369193690936889368793686936859368493683936829368193680936789367793676936759367493673936729367193670936689366793666936659366493663936629366193660936589365793656936559365493653936529365193650936489364793646936459364493643936429364193640936389363793636936359363493633936329363193630936289362793626936259362493623936229362193620936189361793616936159361493613936129361193610936089360793606936059360493603936029360193600935929359193590935889358793586935859358493583935829358193580935789357793576935759357493573935729357193570935689356793566935659356493563935629356193560935589355793556935559355493553935529355193550935489354793546935459354493543935429354193540935389353793536935359353493533935329353193530935289352793526935259352493523935229352193520935189351793516935159351493513935129351193510935089350793506935059350493503935029350193500934929349193490934889348793486934859348493483934829348193480934789347793476934759347493473934729347193470934689346793466934659346493463934629346193460934589345793456934559345493453934529345193450934489344793446934459344493443934429344193440934389343793436934359343493433934329343193430934289342793426934259342493423934229342193420934189341793416934159341493413934129341193410934089340793406934059340493403934029340193400933929339193390933889338793386933859338493383933829338193380933789337793376933759337493373933729337193370933689336793366933659336493363933629336193360933589335793356933559335493353933529335193350933489334793346933459334493343933429334193340933389333793336933359333493333933329333193330933289332793326933259332493323933229332193320933189331793316933159331493313933129331193310933089330793306933059330493303933029330193300932929329193290932889328793286932859328493283932829328193280932789327793276932759327493273932729327193270932689326793266932659326493263932629326193260932589325793256932559325493253932529325193250932489324793246932459324493243932429324193240932389323793236932359323493233932329323193230932289322793226932259322493223932229322193220932189321793216932159321493213932129321193210932089320793206932059320493203932029320193200931929319193190931889318793186931859318493183931829318193180931789317793176931759317493173931729317193170931689316793166931659316493163931629316193160931589315793156931559315493153931529315193150931489314793146931459314493143931429314193140931389313793136931359313493133931329313193130931289312793126931259312493123931229312193120931189311793116931159311493113931129311193110931089310793106931059310493103931029310193100930929309193090930889308793086930859308493083930829308193080930789307793076930759307493073930729307193070930689306793066930659306493063930629306193060930589305793056930559305493053930529305193050930489304793046930459304493043930429304193040930389303793036930359303493033930329303193030930289302793026930259302493023930229302193020930189301793016930159301493013930129301193010930089300793006930059300493003930029300193000929289292792926929259292492923929229292192920929189291792916929159291492913929129291192910929089290792906929059290492903929029290192900928919289092888928879288692885928849288392882928819288092878928779287692875928749287392872928719287092868928679286692865928649286392862928619286092858928579285692855928549285392852928519285092848928479284692845928449284392842928419284092838928379283692835928349283392832928319283092828928279282692825928249282392822928219282092818928179281692815928149281392812928119281092808928079280692805928049280392802928019280092791927909278892787927869278592784927839278292781927809277892777927769277592774927739277292771927709276892767927669276592764927639276292761927609275892757927569275592754927539275292751927509274892747927469274592744927439274292741927409273892737927369273592734927339273292731927309272892727927269272592724927239272292721927209271892717927169271592714927139271292711927109270892707927069270592704927039270292701927009269192690926889268792686926859268492683926829268192680926789267792676926759267492673926729267192670926689266792666926659266492663926629266192660926589265792656926559265492653926529265192650926489264792646926459264492643926429264192640926389263792636926359263492633926329263192630926289262792626926259262492623926229262192620926189261792616926159261492613926129261192610926089260792606926059260492603926029260192600925919259092588925879258692585925849258392582925819258092578925779257692575925749257392572925719257092568925679256692565925649256392562925619256092558925579255692555925549255392552925519255092548925479254692545925449254392542925419254092538925379253692535925349253392532925319253092528925279252692525925249252392522925219252092518925179251692515925149251392512925119251092508925079250692505925049250392502925019250092491924909248892487924869248592484924839248292481924809247892477924769247592474924739247292471924709246892467924669246592464924639246292461924609245892457924569245592454924539245292451924509244892447924469244592444924439244292441924409243892437924369243592434924339243292431924309242892427924269242592424924239242292421924209241892417924169241592414924139241292411924109240892407924069240592404924039240292401924009239192390923889238792386923859238492383923829238192380923789237792376923759237492373923729237192370923689236792366923659236492363923629236192360923589235792356923559235492353923529235192350923489234792346923459234492343923429234192340923389233792336923359233492333923329233192330923289232792326923259232492323923229232192320923189231792316923159231492313923129231192310923089230792306923059230492303923029230192300922919229092288922879228692285922849228392282922819228092278922779227692275922749227392272922719227092268922679226692265922649226392262922619226092258922579225692255922549225392252922519225092248922479224692245922449224392242922419224092238922379223692235922349223392232922319223092228922279222692225922249222392222922219222092218922179221692215922149221392212922119221092208922079220692205922049220392202922019220092191921909218892187921869218592184921839218292181921809217892177921769217592174921739217292171921709216892167921669216592164921639216292161921609215892157921569215592154921539215292151921509214892147921469214592144921439214292141921409213892137921369213592134921339213292131921309212892127921269212592124921239212292121921209211892117921169211592114921139211292111921109210892107921069210592104921039210292101921009209192090920889208792086920859208492083920829208192080920789207792076920759207492073920729207192070920689206792066920659206492063920629206192060920589205792056920559205492053920529205192050920489204792046920459204492043920429204192040920389203792036920359203492033920329203192030920289202792026920259202492023920229202192020920189201792016920159201492013920129201192010920089200792006920059200492003920029200192000919189191791916919159191491913919129191191910919089190791906919059190491903919029190191900918909188891887918869188591884918839188291881918809187891877918769187591874918739187291871918709186891867918669186591864918639186291861918609185891857918569185591854918539185291851918509184891847918469184591844918439184291841918409183891837918369183591834918339183291831918309182891827918269182591824918239182291821918209181891817918169181591814918139181291811918109180891807918069180591804918039180291801918009179091788917879178691785917849178391782917819178091778917779177691775917749177391772917719177091768917679176691765917649176391762917619176091758917579175691755917549175391752917519175091748917479174691745917449174391742917419174091738917379173691735917349173391732917319173091728917279172691725917249172391722917219172091718917179171691715917149171391712917119171091708917079170691705917049170391702917019170091690916889168791686916859168491683916829168191680916789167791676916759167491673916729167191670916689166791666916659166491663916629166191660916589165791656916559165491653916529165191650916489164791646916459164491643916429164191640916389163791636916359163491633916329163191630916289162791626916259162491623916229162191620916189161791616916159161491613916129161191610916089160791606916059160491603916029160191600915909158891587915869158591584915839158291581915809157891577915769157591574915739157291571915709156891567915669156591564915639156291561915609155891557915569155591554915539155291551915509154891547915469154591544915439154291541915409153891537915369153591534915339153291531915309152891527915269152591524915239152291521915209151891517915169151591514915139151291511915109150891507915069150591504915039150291501915009149091488914879148691485914849148391482914819148091478914779147691475914749147391472914719147091468914679146691465914649146391462914619146091458914579145691455914549145391452914519145091448914479144691445914449144391442914419144091438914379143691435914349143391432914319143091428914279142691425914249142391422914219142091418914179141691415914149141391412914119141091408914079140691405914049140391402914019140091390913889138791386913859138491383913829138191380913789137791376913759137491373913729137191370913689136791366913659136491363913629136191360913589135791356913559135491353913529135191350913489134791346913459134491343913429134191340913389133791336913359133491333913329133191330913289132791326913259132491323913229132191320913189131791316913159131491313913129131191310913089130791306913059130491303913029130191300912909128891287912869128591284912839128291281912809127891277912769127591274912739127291271912709126891267912669126591264912639126291261912609125891257912569125591254912539125291251912509124891247912469124591244912439124291241912409123891237912369123591234912339123291231912309122891227912269122591224912239122291221912209121891217912169121591214912139121291211912109120891207912069120591204912039120291201912009119091188911879118691185911849118391182911819118091178911779117691175911749117391172911719117091168911679116691165911649116391162911619116091158911579115691155911549115391152911519115091148911479114691145911449114391142911419114091138911379113691135911349113391132911319113091128911279112691125911249112391122911219112091118911179111691115911149111391112911119111091108911079110691105911049110391102911019110091090910889108791086910859108491083910829108191080910789107791076910759107491073910729107191070910689106791066910659106491063910629106191060910589105791056910559105491053910529105191050910489104791046910459104491043910429104191040910389103791036910359103491033910329103191030910289102791026910259102491023910229102191020910189101791016910159101491013910129101191010910089100791006910059100491003910029100191000909089090790906909059090490903909029090190900908889088790886908859088490883908829088190880908789087790876908759087490873908729087190870908689086790866908659086490863908629086190860908589085790856908559085490853908529085190850908489084790846908459084490843908429084190840908389083790836908359083490833908329083190830908289082790826908259082490823908229082190820908189081790816908159081490813908129081190810908089080790806908059080490803908029080190800907889078790786907859078490783907829078190780907789077790776907759077490773907729077190770907689076790766907659076490763907629076190760907589075790756907559075490753907529075190750907489074790746907459074490743907429074190740907389073790736907359073490733907329073190730907289072790726907259072490723907229072190720907189071790716907159071490713907129071190710907089070790706907059070490703907029070190700906889068790686906859068490683906829068190680906789067790676906759067490673906729067190670906689066790666906659066490663906629066190660906589065790656906559065490653906529065190650906489064790646906459064490643906429064190640906389063790636906359063490633906329063190630906289062790626906259062490623906229062190620906189061790616906159061490613906129061190610906089060790606906059060490603906029060190600905889058790586905859058490583905829058190580905789057790576905759057490573905729057190570905689056790566905659056490563905629056190560905589055790556905559055490553905529055190550905489054790546905459054490543905429054190540905389053790536905359053490533905329053190530905289052790526905259052490523905229052190520905189051790516905159051490513905129051190510905089050790506905059050490503905029050190500904889048790486904859048490483904829048190480904789047790476904759047490473904729047190470904689046790466904659046490463904629046190460904589045790456904559045490453904529045190450904489044790446904459044490443904429044190440904389043790436904359043490433904329043190430904289042790426904259042490423904229042190420904189041790416904159041490413904129041190410904089040790406904059040490403904029040190400903889038790386903859038490383903829038190380903789037790376903759037490373903729037190370903689036790366903659036490363903629036190360903589035790356903559035490353903529035190350903489034790346903459034490343903429034190340903389033790336903359033490333903329033190330903289032790326903259032490323903229032190320903189031790316903159031490313903129031190310903089030790306903059030490303903029030190300902889028790286902859028490283902829028190280902789027790276902759027490273902729027190270902689026790266902659026490263902629026190260902589025790256902559025490253902529025190250902489024790246902459024490243902429024190240902389023790236902359023490233902329023190230902289022790226902259022490223902229022190220902189021790216902159021490213902129021190210902089020790206902059020490203902029020190200901889018790186901859018490183901829018190180901789017790176901759017490173901729017190170901689016790166901659016490163901629016190160901589015790156901559015490153901529015190150901489014790146901459014490143901429014190140901389013790136901359013490133901329013190130901289012790126901259012490123901229012190120901189011790116901159011490113901129011190110901089010790106901059010490103901029010190100900889008790086900859008490083900829008190080900789007790076900759007490073900729007190070900689006790066900659006490063900629006190060900589005790056900559005490053900529005190050900489004790046900459004490043900429004190040900389003790036900359003490033900329003190030900289002790026900259002490023900229002190020900189001790016900159001490013900129001190010900089000790006900059000490003900029000190000888887888868888588884888838888288881888808887788876888758887488873888728887188870888678886688865888648886388862888618886088857888568885588854888538885288851888508884788846888458884488843888428884188840888378883688835888348883388832888318883088827888268882588824888238882288821888208881788816888158881488813888128881188810888078880688805888048880388802888018880088787887868878588784887838878288781887808877788776887758877488773887728877188770887678876688765887648876388762887618876088757887568875588754887538875288751887508874788746887458874488743887428874188740887378873688735887348873388732887318873088727887268872588724887238872288721887208871788716887158871488713887128871188710887078870688705887048870388702887018870088687886868868588684886838868288681886808867788676886758867488673886728867188670886678866688665886648866388662886618866088657886568865588654886538865288651886508864788646886458864488643886428864188640886378863688635886348863388632886318863088627886268862588624886238862288621886208861788616886158861488613886128861188610886078860688605886048860388602886018860088587885868858588584885838858288581885808857788576885758857488573885728857188570885678856688565885648856388562885618856088557885568855588554885538855288551885508854788546885458854488543885428854188540885378853688535885348853388532885318853088527885268852588524885238852288521885208851788516885158851488513885128851188510885078850688505885048850388502885018850088487884868848588484884838848288481884808847788476884758847488473884728847188470884678846688465884648846388462884618846088457884568845588454884538845288451884508844788446884458844488443884428844188440884378843688435884348843388432884318843088427884268842588424884238842288421884208841788416884158841488413884128841188410884078840688405884048840388402884018840088387883868838588384883838838288381883808837788376883758837488373883728837188370883678836688365883648836388362883618836088357883568835588354883538835288351883508834788346883458834488343883428834188340883378833688335883348833388332883318833088327883268832588324883238832288321883208831788316883158831488313883128831188310883078830688305883048830388302883018830088287882868828588284882838828288281882808827788276882758827488273882728827188270882678826688265882648826388262882618826088257882568825588254882538825288251882508824788246882458824488243882428824188240882378823688235882348823388232882318823088227882268822588224882238822288221882208821788216882158821488213882128821188210882078820688205882048820388202882018820088187881868818588184881838818288181881808817788176881758817488173881728817188170881678816688165881648816388162881618816088157881568815588154881538815288151881508814788146881458814488143881428814188140881378813688135881348813388132881318813088127881268812588124881238812288121881208811788116881158811488113881128811188110881078810688105881048810388102881018810088087880868808588084880838808288081880808807788076880758807488073880728807188070880678806688065880648806388062880618806088057880568805588054880538805288051880508804788046880458804488043880428804188040880378803688035880348803388032880318803088027880268802588024880238802288021880208801788016880158801488013880128801188010880078800688005880048800388002880018800087877878768787587874878738787287871878708786787866878658786487863878628786187860878578785687855878548785387852878518785087847878468784587844878438784287841878408783787836878358783487833878328783187830878278782687825878248782387822878218782087817878168781587814878138781287811878108780787806878058780487803878028780187800877868778587784877838778287781877808777787776877758777487773877728777187770877678776687765877648776387762877618776087757877568775587754877538775287751877508774787746877458774487743877428774187740877378773687735877348773387732877318773087727877268772587724877238772287721877208771787716877158771487713877128771187710877078770687705877048770387702877018770087686876858768487683876828768187680876778767687675876748767387672876718767087667876668766587664876638766287661876608765787656876558765487653876528765187650876478764687645876448764387642876418764087637876368763587634876338763287631876308762787626876258762487623876228762187620876178761687615876148761387612876118761087607876068760587604876038760287601876008758687585875848758387582875818758087577875768757587574875738757287571875708756787566875658756487563875628756187560875578755687555875548755387552875518755087547875468754587544875438754287541875408753787536875358753487533875328753187530875278752687525875248752387522875218752087517875168751587514875138751287511875108750787506875058750487503875028750187500874868748587484874838748287481874808747787476874758747487473874728747187470874678746687465874648746387462874618746087457874568745587454874538745287451874508744787446874458744487443874428744187440874378743687435874348743387432874318743087427874268742587424874238742287421874208741787416874158741487413874128741187410874078740687405874048740387402874018740087386873858738487383873828738187380873778737687375873748737387372873718737087367873668736587364873638736287361873608735787356873558735487353873528735187350873478734687345873448734387342873418734087337873368733587334873338733287331873308732787326873258732487323873228732187320873178731687315873148731387312873118731087307873068730587304873038730287301873008728687285872848728387282872818728087277872768727587274872738727287271872708726787266872658726487263872628726187260872578725687255872548725387252872518725087247872468724587244872438724287241872408723787236872358723487233872328723187230872278722687225872248722387222872218722087217872168721587214872138721287211872108720787206872058720487203872028720187200871868718587184871838718287181871808717787176871758717487173871728717187170871678716687165871648716387162871618716087157871568715587154871538715287151871508714787146871458714487143871428714187140871378713687135871348713387132871318713087127871268712587124871238712287121871208711787116871158711487113871128711187110871078710687105871048710387102871018710087086870858708487083870828708187080870778707687075870748707387072870718707087067870668706587064870638706287061870608705787056870558705487053870528705187050870478704687045870448704387042870418704087037870368703587034870338703287031870308702787026870258702487023870228702187020870178701687015870148701387012870118701087007870068700587004870038700287001870008686786866868658686486863868628686186860868578685686855868548685386852868518685086847868468684586844868438684286841868408683786836868358683486833868328683186830868278682686825868248682386822868218682086817868168681586814868138681286811868108680786806868058680486803868028680186800867858678486783867828678186780867778677686775867748677386772867718677086767867668676586764867638676286761867608675786756867558675486753867528675186750867478674686745867448674386742867418674086737867368673586734867338673286731867308672786726867258672486723867228672186720867178671686715867148671386712867118671086707867068670586704867038670286701867008668586684866838668286681866808667786676866758667486673866728667186670866678666686665866648666386662866618666086657866568665586654866538665286651866508664786646866458664486643866428664186640866378663686635866348663386632866318663086627866268662586624866238662286621866208661786616866158661486613866128661186610866078660686605866048660386602866018660086585865848658386582865818658086577865768657586574865738657286571865708656786566865658656486563865628656186560865578655686555865548655386552865518655086547865468654586544865438654286541865408653786536865358653486533865328653186530865278652686525865248652386522865218652086517865168651586514865138651286511865108650786506865058650486503865028650186500864858648486483864828648186480864778647686475864748647386472864718647086467864668646586464864638646286461864608645786456864558645486453864528645186450864478644686445864448644386442864418644086437864368643586434864338643286431864308642786426864258642486423864228642186420864178641686415864148641386412864118641086407864068640586404864038640286401864008638586384863838638286381863808637786376863758637486373863728637186370863678636686365863648636386362863618636086357863568635586354863538635286351863508634786346863458634486343863428634186340863378633686335863348633386332863318633086327863268632586324863238632286321863208631786316863158631486313863128631186310863078630686305863048630386302863018630086285862848628386282862818628086277862768627586274862738627286271862708626786266862658626486263862628626186260862578625686255862548625386252862518625086247862468624586244862438624286241862408623786236862358623486233862328623186230862278622686225862248622386222862218622086217862168621586214862138621286211862108620786206862058620486203862028620186200861858618486183861828618186180861778617686175861748617386172861718617086167861668616586164861638616286161861608615786156861558615486153861528615186150861478614686145861448614386142861418614086137861368613586134861338613286131861308612786126861258612486123861228612186120861178611686115861148611386112861118611086107861068610586104861038610286101861008608586084860838608286081860808607786076860758607486073860728607186070860678606686065860648606386062860618606086057860568605586054860538605286051860508604786046860458604486043860428604186040860378603686035860348603386032860318603086027860268602586024860238602286021860208601786016860158601486013860128601186010860078600686005860048600386002860018600085857858568585585854858538585285851858508584785846858458584485843858428584185840858378583685835858348583385832858318583085827858268582585824858238582285821858208581785816858158581485813858128581185810858078580685805858048580385802858018580085784857838578285781857808577785776857758577485773857728577185770857678576685765857648576385762857618576085757857568575585754857538575285751857508574785746857458574485743857428574185740857378573685735857348573385732857318573085727857268572585724857238572285721857208571785716857158571485713857128571185710857078570685705857048570385702857018570085684856838568285681856808567785676856758567485673856728567185670856678566685665856648566385662856618566085657856568565585654856538565285651856508564785646856458564485643856428564185640856378563685635856348563385632856318563085627856268562585624856238562285621856208561785616856158561485613856128561185610856078560685605856048560385602856018560085584855838558285581855808557785576855758557485573855728557185570855678556685565855648556385562855618556085557855568555585554855538555285551855508554785546855458554485543855428554185540855378553685535855348553385532855318553085527855268552585524855238552285521855208551785516855158551485513855128551185510855078550685505855048550385502855018550085484854838548285481854808547785476854758547485473854728547185470854678546685465854648546385462854618546085457854568545585454854538545285451854508544785446854458544485443854428544185440854378543685435854348543385432854318543085427854268542585424854238542285421854208541785416854158541485413854128541185410854078540685405854048540385402854018540085384853838538285381853808537785376853758537485373853728537185370853678536685365853648536385362853618536085357853568535585354853538535285351853508534785346853458534485343853428534185340853378533685335853348533385332853318533085327853268532585324853238532285321853208531785316853158531485313853128531185310853078530685305853048530385302853018530085284852838528285281852808527785276852758527485273852728527185270852678526685265852648526385262852618526085257852568525585254852538525285251852508524785246852458524485243852428524185240852378523685235852348523385232852318523085227852268522585224852238522285221852208521785216852158521485213852128521185210852078520685205852048520385202852018520085184851838518285181851808517785176851758517485173851728517185170851678516685165851648516385162851618516085157851568515585154851538515285151851508514785146851458514485143851428514185140851378513685135851348513385132851318513085127851268512585124851238512285121851208511785116851158511485113851128511185110851078510685105851048510385102851018510085084850838508285081850808507785076850758507485073850728507185070850678506685065850648506385062850618506085057850568505585054850538505285051850508504785046850458504485043850428504185040850378503685035850348503385032850318503085027850268502585024850238502285021850208501785016850158501485013850128501185010850078500685005850048500385002850018500084847848468484584844848438484284841848408483784836848358483484833848328483184830848278482684825848248482384822848218482084817848168481584814848138481284811848108480784806848058480484803848028480184800847838478284781847808477784776847758477484773847728477184770847678476684765847648476384762847618476084757847568475584754847538475284751847508474784746847458474484743847428474184740847378473684735847348473384732847318473084727847268472584724847238472284721847208471784716847158471484713847128471184710847078470684705847048470384702847018470084683846828468184680846778467684675846748467384672846718467084667846668466584664846638466284661846608465784656846558465484653846528465184650846478464684645846448464384642846418464084637846368463584634846338463284631846308462784626846258462484623846228462184620846178461684615846148461384612846118461084607846068460584604846038460284601846008458384582845818458084577845768457584574845738457284571845708456784566845658456484563845628456184560845578455684555845548455384552845518455084547845468454584544845438454284541845408453784536845358453484533845328453184530845278452684525845248452384522845218452084517845168451584514845138451284511845108450784506845058450484503845028450184500844838448284481844808447784476844758447484473844728447184470844678446684465844648446384462844618446084457844568445584454844538445284451844508444784446844458444484443844428444184440844378443684435844348443384432844318443084427844268442584424844238442284421844208441784416844158441484413844128441184410844078440684405844048440384402844018440084383843828438184380843778437684375843748437384372843718437084367843668436584364843638436284361843608435784356843558435484353843528435184350843478434684345843448434384342843418434084337843368433584334843338433284331843308432784326843258432484323843228432184320843178431684315843148431384312843118431084307843068430584304843038430284301843008428384282842818428084277842768427584274842738427284271842708426784266842658426484263842628426184260842578425684255842548425384252842518425084247842468424584244842438424284241842408423784236842358423484233842328423184230842278422684225842248422384222842218422084217842168421584214842138421284211842108420784206842058420484203842028420184200841838418284181841808417784176841758417484173841728417184170841678416684165841648416384162841618416084157841568415584154841538415284151841508414784146841458414484143841428414184140841378413684135841348413384132841318413084127841268412584124841238412284121841208411784116841158411484113841128411184110841078410684105841048410384102841018410084083840828408184080840778407684075840748407384072840718407084067840668406584064840638406284061840608405784056840558405484053840528405184050840478404684045840448404384042840418404084037840368403584034840338403284031840308402784026840258402484023840228402184020840178401684015840148401384012840118401084007840068400584004840038400284001840008383783836838358383483833838328383183830838278382683825838248382383822838218382083817838168381583814838138381283811838108380783806838058380483803838028380183800837828378183780837778377683775837748377383772837718377083767837668376583764837638376283761837608375783756837558375483753837528375183750837478374683745837448374383742837418374083737837368373583734837338373283731837308372783726837258372483723837228372183720837178371683715837148371383712837118371083707837068370583704837038370283701837008368283681836808367783676836758367483673836728367183670836678366683665836648366383662836618366083657836568365583654836538365283651836508364783646836458364483643836428364183640836378363683635836348363383632836318363083627836268362583624836238362283621836208361783616836158361483613836128361183610836078360683605836048360383602836018360083582835818358083577835768357583574835738357283571835708356783566835658356483563835628356183560835578355683555835548355383552835518355083547835468354583544835438354283541835408353783536835358353483533835328353183530835278352683525835248352383522835218352083517835168351583514835138351283511835108350783506835058350483503835028350183500834828348183480834778347683475834748347383472834718347083467834668346583464834638346283461834608345783456834558345483453834528345183450834478344683445834448344383442834418344083437834368343583434834338343283431834308342783426834258342483423834228342183420834178341683415834148341383412834118341083407834068340583404834038340283401834008338283381833808337783376833758337483373833728337183370833678336683365833648336383362833618336083357833568335583354833538335283351833508334783346833458334483343833428334183340833378333683335833348333383332833318333083327833268332583324833238332283321833208331783316833158331483313833128331183310833078330683305833048330383302833018330083282832818328083277832768327583274832738327283271832708326783266832658326483263832628326183260832578325683255832548325383252832518325083247832468324583244832438324283241832408323783236832358323483233832328323183230832278322683225832248322383222832218322083217832168321583214832138321283211832108320783206832058320483203832028320183200831828318183180831778317683175831748317383172831718317083167831668316583164831638316283161831608315783156831558315483153831528315183150831478314683145831448314383142831418314083137831368313583134831338313283131831308312783126831258312483123831228312183120831178311683115831148311383112831118311083107831068310583104831038310283101831008308283081830808307783076830758307483073830728307183070830678306683065830648306383062830618306083057830568305583054830538305283051830508304783046830458304483043830428304183040830378303683035830348303383032830318303083027830268302583024830238302283021830208301783016830158301483013830128301183010830078300683005830048300383002830018300082827828268282582824828238282282821828208281782816828158281482813828128281182810828078280682805828048280382802828018280082781827808277782776827758277482773827728277182770827678276682765827648276382762827618276082757827568275582754827538275282751827508274782746827458274482743827428274182740827378273682735827348273382732827318273082727827268272582724827238272282721827208271782716827158271482713827128271182710827078270682705827048270382702827018270082681826808267782676826758267482673826728267182670826678266682665826648266382662826618266082657826568265582654826538265282651826508264782646826458264482643826428264182640826378263682635826348263382632826318263082627826268262582624826238262282621826208261782616826158261482613826128261182610826078260682605826048260382602826018260082581825808257782576825758257482573825728257182570825678256682565825648256382562825618256082557825568255582554825538255282551825508254782546825458254482543825428254182540825378253682535825348253382532825318253082527825268252582524825238252282521825208251782516825158251482513825128251182510825078250682505825048250382502825018250082481824808247782476824758247482473824728247182470824678246682465824648246382462824618246082457824568245582454824538245282451824508244782446824458244482443824428244182440824378243682435824348243382432824318243082427824268242582424824238242282421824208241782416824158241482413824128241182410824078240682405824048240382402824018240082381823808237782376823758237482373823728237182370823678236682365823648236382362823618236082357823568235582354823538235282351823508234782346823458234482343823428234182340823378233682335823348233382332823318233082327823268232582324823238232282321823208231782316823158231482313823128231182310823078230682305823048230382302823018230082281822808227782276822758227482273822728227182270822678226682265822648226382262822618226082257822568225582254822538225282251822508224782246822458224482243822428224182240822378223682235822348223382232822318223082227822268222582224822238222282221822208221782216822158221482213822128221182210822078220682205822048220382202822018220082181821808217782176821758217482173821728217182170821678216682165821648216382162821618216082157821568215582154821538215282151821508214782146821458214482143821428214182140821378213682135821348213382132821318213082127821268212582124821238212282121821208211782116821158211482113821128211182110821078210682105821048210382102821018210082081820808207782076820758207482073820728207182070820678206682065820648206382062820618206082057820568205582054820538205282051820508204782046820458204482043820428204182040820378203682035820348203382032820318203082027820268202582024820238202282021820208201782016820158201482013820128201182010820078200682005820048200382002820018200081817818168181581814818138181281811818108180781806818058180481803818028180181800817808177781776817758177481773817728177181770817678176681765817648176381762817618176081757817568175581754817538175281751817508174781746817458174481743817428174181740817378173681735817348173381732817318173081727817268172581724817238172281721817208171781716817158171481713817128171181710817078170681705817048170381702817018170081680816778167681675816748167381672816718167081667816668166581664816638166281661816608165781656816558165481653816528165181650816478164681645816448164381642816418164081637816368163581634816338163281631816308162781626816258162481623816228162181620816178161681615816148161381612816118161081607816068160581604816038160281601816008158081577815768157581574815738157281571815708156781566815658156481563815628156181560815578155681555815548155381552815518155081547815468154581544815438154281541815408153781536815358153481533815328153181530815278152681525815248152381522815218152081517815168151581514815138151281511815108150781506815058150481503815028150181500814808147781476814758147481473814728147181470814678146681465814648146381462814618146081457814568145581454814538145281451814508144781446814458144481443814428144181440814378143681435814348143381432814318143081427814268142581424814238142281421814208141781416814158141481413814128141181410814078140681405814048140381402814018140081380813778137681375813748137381372813718137081367813668136581364813638136281361813608135781356813558135481353813528135181350813478134681345813448134381342813418134081337813368133581334813338133281331813308132781326813258132481323813228132181320813178131681315813148131381312813118131081307813068130581304813038130281301813008128081277812768127581274812738127281271812708126781266812658126481263812628126181260812578125681255812548125381252812518125081247812468124581244812438124281241812408123781236812358123481233812328123181230812278122681225812248122381222812218122081217812168121581214812138121281211812108120781206812058120481203812028120181200811808117781176811758117481173811728117181170811678116681165811648116381162811618116081157811568115581154811538115281151811508114781146811458114481143811428114181140811378113681135811348113381132811318113081127811268112581124811238112281121811208111781116811158111481113811128111181110811078110681105811048110381102811018110081080810778107681075810748107381072810718107081067810668106581064810638106281061810608105781056810558105481053810528105181050810478104681045810448104381042810418104081037810368103581034810338103281031810308102781026810258102481023810228102181020810178101681015810148101381012810118101081007810068100581004810038100281001810008080780806808058080480803808028080180800807778077680775807748077380772807718077080767807668076580764807638076280761807608075780756807558075480753807528075180750807478074680745807448074380742807418074080737807368073580734807338073280731807308072780726807258072480723807228072180720807178071680715807148071380712807118071080707807068070580704807038070280701807008067780676806758067480673806728067180670806678066680665806648066380662806618066080657806568065580654806538065280651806508064780646806458064480643806428064180640806378063680635806348063380632806318063080627806268062580624806238062280621806208061780616806158061480613806128061180610806078060680605806048060380602806018060080577805768057580574805738057280571805708056780566805658056480563805628056180560805578055680555805548055380552805518055080547805468054580544805438054280541805408053780536805358053480533805328053180530805278052680525805248052380522805218052080517805168051580514805138051280511805108050780506805058050480503805028050180500804778047680475804748047380472804718047080467804668046580464804638046280461804608045780456804558045480453804528045180450804478044680445804448044380442804418044080437804368043580434804338043280431804308042780426804258042480423804228042180420804178041680415804148041380412804118041080407804068040580404804038040280401804008037780376803758037480373803728037180370803678036680365803648036380362803618036080357803568035580354803538035280351803508034780346803458034480343803428034180340803378033680335803348033380332803318033080327803268032580324803238032280321803208031780316803158031480313803128031180310803078030680305803048030380302803018030080277802768027580274802738027280271802708026780266802658026480263802628026180260802578025680255802548025380252802518025080247802468024580244802438024280241802408023780236802358023480233802328023180230802278022680225802248022380222802218022080217802168021580214802138021280211802108020780206802058020480203802028020180200801778017680175801748017380172801718017080167801668016580164801638016280161801608015780156801558015480153801528015180150801478014680145801448014380142801418014080137801368013580134801338013280131801308012780126801258012480123801228012180120801178011680115801148011380112801118011080107801068010580104801038010280101801008007780076800758007480073800728007180070800678006680065800648006380062800618006080057800568005580054800538005280051800508004780046800458004480043800428004180040800378003680035800348003380032800318003080027800268002580024800238002280021800208001780016800158001480013800128001180010800078000680005800048000380002800018000077777677775777747777377772777717777077766777657776477763777627776177760777567775577754777537775277751777507774677745777447774377742777417774077736777357773477733777327773177730777267772577724777237772277721777207771677715777147771377712777117771077706777057770477703777027770177700776767767577674776737767277671776707766677665776647766377662776617766077656776557765477653776527765177650776467764577644776437764277641776407763677635776347763377632776317763077626776257762477623776227762177620776167761577614776137761277611776107760677605776047760377602776017760077576775757757477573775727757177570775667756577564775637756277561775607755677555775547755377552775517755077546775457754477543775427754177540775367753577534775337753277531775307752677525775247752377522775217752077516775157751477513775127751177510775067750577504775037750277501775007747677475774747747377472774717747077466774657746477463774627746177460774567745577454774537745277451774507744677445774447744377442774417744077436774357743477433774327743177430774267742577424774237742277421774207741677415774147741377412774117741077406774057740477403774027740177400773767737577374773737737277371773707736677365773647736377362773617736077356773557735477353773527735177350773467734577344773437734277341773407733677335773347733377332773317733077326773257732477323773227732177320773167731577314773137731277311773107730677305773047730377302773017730077276772757727477273772727727177270772667726577264772637726277261772607725677255772547725377252772517725077246772457724477243772427724177240772367723577234772337723277231772307722677225772247722377222772217722077216772157721477213772127721177210772067720577204772037720277201772007717677175771747717377172771717717077166771657716477163771627716177160771567715577154771537715277151771507714677145771447714377142771417714077136771357713477133771327713177130771267712577124771237712277121771207711677115771147711377112771117711077106771057710477103771027710177100770767707577074770737707277071770707706677065770647706377062770617706077056770557705477053770527705177050770467704577044770437704277041770407703677035770347703377032770317703077026770257702477023770227702177020770167701577014770137701277011770107700677005770047700377002770017700076766767657676476763767627676176760767567675576754767537675276751767507674676745767447674376742767417674076736767357673476733767327673176730767267672576724767237672276721767207671676715767147671376712767117671076706767057670476703767027670176700766757667476673766727667176670766667666576664766637666276661766607665676655766547665376652766517665076646766457664476643766427664176640766367663576634766337663276631766307662676625766247662376622766217662076616766157661476613766127661176610766067660576604766037660276601766007657576574765737657276571765707656676565765647656376562765617656076556765557655476553765527655176550765467654576544765437654276541765407653676535765347653376532765317653076526765257652476523765227652176520765167651576514765137651276511765107650676505765047650376502765017650076475764747647376472764717647076466764657646476463764627646176460764567645576454764537645276451764507644676445764447644376442764417644076436764357643476433764327643176430764267642576424764237642276421764207641676415764147641376412764117641076406764057640476403764027640176400763757637476373763727637176370763667636576364763637636276361763607635676355763547635376352763517635076346763457634476343763427634176340763367633576334763337633276331763307632676325763247632376322763217632076316763157631476313763127631176310763067630576304763037630276301763007627576274762737627276271762707626676265762647626376262762617626076256762557625476253762527625176250762467624576244762437624276241762407623676235762347623376232762317623076226762257622476223762227622176220762167621576214762137621276211762107620676205762047620376202762017620076175761747617376172761717617076166761657616476163761627616176160761567615576154761537615276151761507614676145761447614376142761417614076136761357613476133761327613176130761267612576124761237612276121761207611676115761147611376112761117611076106761057610476103761027610176100760757607476073760727607176070760667606576064760637606276061760607605676055760547605376052760517605076046760457604476043760427604176040760367603576034760337603276031760307602676025760247602376022760217602076016760157601476013760127601176010760067600576004760037600276001760007575675755757547575375752757517575075746757457574475743757427574175740757367573575734757337573275731757307572675725757247572375722757217572075716757157571475713757127571175710757067570575704757037570275701757007567475673756727567175670756667566575664756637566275661756607565675655756547565375652756517565075646756457564475643756427564175640756367563575634756337563275631756307562675625756247562375622756217562075616756157561475613756127561175610756067560575604756037560275601756007557475573755727557175570755667556575564755637556275561755607555675555755547555375552755517555075546755457554475543755427554175540755367553575534755337553275531755307552675525755247552375522755217552075516755157551475513755127551175510755067550575504755037550275501755007547475473754727547175470754667546575464754637546275461754607545675455754547545375452754517545075446754457544475443754427544175440754367543575434754337543275431754307542675425754247542375422754217542075416754157541475413754127541175410754067540575404754037540275401754007537475373753727537175370753667536575364753637536275361753607535675355753547535375352753517535075346753457534475343753427534175340753367533575334753337533275331753307532675325753247532375322753217532075316753157531475313753127531175310753067530575304753037530275301753007527475273752727527175270752667526575264752637526275261752607525675255752547525375252752517525075246752457524475243752427524175240752367523575234752337523275231752307522675225752247522375222752217522075216752157521475213752127521175210752067520575204752037520275201752007517475173751727517175170751667516575164751637516275161751607515675155751547515375152751517515075146751457514475143751427514175140751367513575134751337513275131751307512675125751247512375122751217512075116751157511475113751127511175110751067510575104751037510275101751007507475073750727507175070750667506575064750637506275061750607505675055750547505375052750517505075046750457504475043750427504175040750367503575034750337503275031750307502675025750247502375022750217502075016750157501475013750127501175010750067500575004750037500275001750007474674745747447474374742747417474074736747357473474733747327473174730747267472574724747237472274721747207471674715747147471374712747117471074706747057470474703747027470174700746737467274671746707466674665746647466374662746617466074656746557465474653746527465174650746467464574644746437464274641746407463674635746347463374632746317463074626746257462474623746227462174620746167461574614746137461274611746107460674605746047460374602746017460074573745727457174570745667456574564745637456274561745607455674555745547455374552745517455074546745457454474543745427454174540745367453574534745337453274531745307452674525745247452374522745217452074516745157451474513745127451174510745067450574504745037450274501745007447374472744717447074466744657446474463744627446174460744567445574454744537445274451744507444674445744447444374442744417444074436744357443474433744327443174430744267442574424744237442274421744207441674415744147441374412744117441074406744057440474403744027440174400743737437274371743707436674365743647436374362743617436074356743557435474353743527435174350743467434574344743437434274341743407433674335743347433374332743317433074326743257432474323743227432174320743167431574314743137431274311743107430674305743047430374302743017430074273742727427174270742667426574264742637426274261742607425674255742547425374252742517425074246742457424474243742427424174240742367423574234742337423274231742307422674225742247422374222742217422074216742157421474213742127421174210742067420574204742037420274201742007417374172741717417074166741657416474163741627416174160741567415574154741537415274151741507414674145741447414374142741417414074136741357413474133741327413174130741267412574124741237412274121741207411674115741147411374112741117411074106741057410474103741027410174100740737407274071740707406674065740647406374062740617406074056740557405474053740527405174050740467404574044740437404274041740407403674035740347403374032740317403074026740257402474023740227402174020740167401574014740137401274011740107400674005740047400374002740017400073736737357373473733737327373173730737267372573724737237372273721737207371673715737147371373712737117371073706737057370473703737027370173700736727367173670736667366573664736637366273661736607365673655736547365373652736517365073646736457364473643736427364173640736367363573634736337363273631736307362673625736247362373622736217362073616736157361473613736127361173610736067360573604736037360273601736007357273571735707356673565735647356373562735617356073556735557355473553735527355173550735467354573544735437354273541735407353673535735347353373532735317353073526735257352473523735227352173520735167351573514735137351273511735107350673505735047350373502735017350073472734717347073466734657346473463734627346173460734567345573454734537345273451734507344673445734447344373442734417344073436734357343473433734327343173430734267342573424734237342273421734207341673415734147341373412734117341073406734057340473403734027340173400733727337173370733667336573364733637336273361733607335673355733547335373352733517335073346733457334473343733427334173340733367333573334733337333273331733307332673325733247332373322733217332073316733157331473313733127331173310733067330573304733037330273301733007327273271732707326673265732647326373262732617326073256732557325473253732527325173250732467324573244732437324273241732407323673235732347323373232732317323073226732257322473223732227322173220732167321573214732137321273211732107320673205732047320373202732017320073172731717317073166731657316473163731627316173160731567315573154731537315273151731507314673145731447314373142731417314073136731357313473133731327313173130731267312573124731237312273121731207311673115731147311373112731117311073106731057310473103731027310173100730727307173070730667306573064730637306273061730607305673055730547305373052730517305073046730457304473043730427304173040730367303573034730337303273031730307302673025730247302373022730217302073016730157301473013730127301173010730067300573004730037300273001730007272672725727247272372722727217272072716727157271472713727127271172710727067270572704727037270272701727007267172670726667266572664726637266272661726607265672655726547265372652726517265072646726457264472643726427264172640726367263572634726337263272631726307262672625726247262372622726217262072616726157261472613726127261172610726067260572604726037260272601726007257172570725667256572564725637256272561725607255672555725547255372552725517255072546725457254472543725427254172540725367253572534725337253272531725307252672525725247252372522725217252072516725157251472513725127251172510725067250572504725037250272501725007247172470724667246572464724637246272461724607245672455724547245372452724517245072446724457244472443724427244172440724367243572434724337243272431724307242672425724247242372422724217242072416724157241472413724127241172410724067240572404724037240272401724007237172370723667236572364723637236272361723607235672355723547235372352723517235072346723457234472343723427234172340723367233572334723337233272331723307232672325723247232372322723217232072316723157231472313723127231172310723067230572304723037230272301723007227172270722667226572264722637226272261722607225672255722547225372252722517225072246722457224472243722427224172240722367223572234722337223272231722307222672225722247222372222722217222072216722157221472213722127221172210722067220572204722037220272201722007217172170721667216572164721637216272161721607215672155721547215372152721517215072146721457214472143721427214172140721367213572134721337213272131721307212672125721247212372122721217212072116721157211472113721127211172110721067210572104721037210272101721007207172070720667206572064720637206272061720607205672055720547205372052720517205072046720457204472043720427204172040720367203572034720337203272031720307202672025720247202372022720217202072016720157201472013720127201172010720067200572004720037200272001720007171671715717147171371712717117171071706717057170471703717027170171700716707166671665716647166371662716617166071656716557165471653716527165171650716467164571644716437164271641716407163671635716347163371632716317163071626716257162471623716227162171620716167161571614716137161271611716107160671605716047160371602716017160071570715667156571564715637156271561715607155671555715547155371552715517155071546715457154471543715427154171540715367153571534715337153271531715307152671525715247152371522715217152071516715157151471513715127151171510715067150571504715037150271501715007147071466714657146471463714627146171460714567145571454714537145271451714507144671445714447144371442714417144071436714357143471433714327143171430714267142571424714237142271421714207141671415714147141371412714117141071406714057140471403714027140171400713707136671365713647136371362713617136071356713557135471353713527135171350713467134571344713437134271341713407133671335713347133371332713317133071326713257132471323713227132171320713167131571314713137131271311713107130671305713047130371302713017130071270712667126571264712637126271261712607125671255712547125371252712517125071246712457124471243712427124171240712367123571234712337123271231712307122671225712247122371222712217122071216712157121471213712127121171210712067120571204712037120271201712007117071166711657116471163711627116171160711567115571154711537115271151711507114671145711447114371142711417114071136711357113471133711327113171130711267112571124711237112271121711207111671115711147111371112711117111071106711057110471103711027110171100710707106671065710647106371062710617106071056710557105471053710527105171050710467104571044710437104271041710407103671035710347103371032710317103071026710257102471023710227102171020710167101571014710137101271011710107100671005710047100371002710017100070706707057070470703707027070170700706667066570664706637066270661706607065670655706547065370652706517065070646706457064470643706427064170640706367063570634706337063270631706307062670625706247062370622706217062070616706157061470613706127061170610706067060570604706037060270601706007056670565705647056370562705617056070556705557055470553705527055170550705467054570544705437054270541705407053670535705347053370532705317053070526705257052470523705227052170520705167051570514705137051270511705107050670505705047050370502705017050070466704657046470463704627046170460704567045570454704537045270451704507044670445704447044370442704417044070436704357043470433704327043170430704267042570424704237042270421704207041670415704147041370412704117041070406704057040470403704027040170400703667036570364703637036270361703607035670355703547035370352703517035070346703457034470343703427034170340703367033570334703337033270331703307032670325703247032370322703217032070316703157031470313703127031170310703067030570304703037030270301703007026670265702647026370262702617026070256702557025470253702527025170250702467024570244702437024270241702407023670235702347023370232702317023070226702257022470223702227022170220702167021570214702137021270211702107020670205702047020370202702017020070166701657016470163701627016170160701567015570154701537015270151701507014670145701447014370142701417014070136701357013470133701327013170130701267012570124701237012270121701207011670115701147011370112701117011070106701057010470103701027010170100700667006570064700637006270061700607005670055700547005370052700517005070046700457004470043700427004170040700367003570034700337003270031700307002670025700247002370022700217002070016700157001470013700127001170010700067000570004700037000270001700006666656666466663666626666166660666556665466653666526665166650666456664466643666426664166640666356663466633666326663166630666256662466623666226662166620666156661466613666126661166610666056660466603666026660166600665656656466563665626656166560665556655466553665526655166550665456654466543665426654166540665356653466533665326653166530665256652466523665226652166520665156651466513665126651166510665056650466503665026650166500664656646466463664626646166460664556645466453664526645166450664456644466443664426644166440664356643466433664326643166430664256642466423664226642166420664156641466413664126641166410664056640466403664026640166400663656636466363663626636166360663556635466353663526635166350663456634466343663426634166340663356633466333663326633166330663256632466323663226632166320663156631466313663126631166310663056630466303663026630166300662656626466263662626626166260662556625466253662526625166250662456624466243662426624166240662356623466233662326623166230662256622466223662226622166220662156621466213662126621166210662056620466203662026620166200661656616466163661626616166160661556615466153661526615166150661456614466143661426614166140661356613466133661326613166130661256612466123661226612166120661156611466113661126611166110661056610466103661026610166100660656606466063660626606166060660556605466053660526605166050660456604466043660426604166040660356603466033660326603166030660256602466023660226602166020660156601466013660126601166010660056600466003660026600166000656556565465653656526565165650656456564465643656426564165640656356563465633656326563165630656256562465623656226562165620656156561465613656126561165610656056560465603656026560165600655646556365562655616556065555655546555365552655516555065545655446554365542655416554065535655346553365532655316553065525655246552365522655216552065515655146551365512655116551065505655046550365502655016550065464654636546265461654606545565454654536545265451654506544565444654436544265441654406543565434654336543265431654306542565424654236542265421654206541565414654136541265411654106540565404654036540265401654006536465363653626536165360653556535465353653526535165350653456534465343653426534165340653356533465333653326533165330653256532465323653226532165320653156531465313653126531165310653056530465303653026530165300652646526365262652616526065255652546525365252652516525065245652446524365242652416524065235652346523365232652316523065225652246522365222652216522065215652146521365212652116521065205652046520365202652016520065164651636516265161651606515565154651536515265151651506514565144651436514265141651406513565134651336513265131651306512565124651236512265121651206511565114651136511265111651106510565104651036510265101651006506465063650626506165060650556505465053650526505165050650456504465043650426504165040650356503465033650326503165030650256502465023650226502165020650156501465013650126501165010650056500465003650026500165000646456464464643646426464164640646356463464633646326463164630646256462464623646226462164620646156461464613646126461164610646056460464603646026460164600645636456264561645606455564554645536455264551645506454564544645436454264541645406453564534645336453264531645306452564524645236452264521645206451564514645136451264511645106450564504645036450264501645006446364462644616446064455644546445364452644516445064445644446444364442644416444064435644346443364432644316443064425644246442364422644216442064415644146441364412644116441064405644046440364402644016440064363643626436164360643556435464353643526435164350643456434464343643426434164340643356433464333643326433164330643256432464323643226432164320643156431464313643126431164310643056430464303643026430164300642636426264261642606425564254642536425264251642506424564244642436424264241642406423564234642336423264231642306422564224642236422264221642206421564214642136421264211642106420564204642036420264201642006416364162641616416064155641546415364152641516415064145641446414364142641416414064135641346413364132641316413064125641246412364122641216412064115641146411364112641116411064105641046410364102641016410064063640626406164060640556405464053640526405164050640456404464043640426404164040640356403464033640326403164030640256402464023640226402164020640156401464013640126401164010640056400464003640026400164000636356363463633636326363163630636256362463623636226362163620636156361463613636126361163610636056360463603636026360163600635626356163560635556355463553635526355163550635456354463543635426354163540635356353463533635326353163530635256352463523635226352163520635156351463513635126351163510635056350463503635026350163500634626346163460634556345463453634526345163450634456344463443634426344163440634356343463433634326343163430634256342463423634226342163420634156341463413634126341163410634056340463403634026340163400633626336163360633556335463353633526335163350633456334463343633426334163340633356333463333633326333163330633256332463323633226332163320633156331463313633126331163310633056330463303633026330163300632626326163260632556325463253632526325163250632456324463243632426324163240632356323463233632326323163230632256322463223632226322163220632156321463213632126321163210632056320463203632026320163200631626316163160631556315463153631526315163150631456314463143631426314163140631356313463133631326313163130631256312463123631226312163120631156311463113631126311163110631056310463103631026310163100630626306163060630556305463053630526305163050630456304463043630426304163040630356303463033630326303163030630256302463023630226302163020630156301463013630126301163010630056300463003630026300163000626256262462623626226262162620626156261462613626126261162610626056260462603626026260162600625616256062555625546255362552625516255062545625446254362542625416254062535625346253362532625316253062525625246252362522625216252062515625146251362512625116251062505625046250362502625016250062461624606245562454624536245262451624506244562444624436244262441624406243562434624336243262431624306242562424624236242262421624206241562414624136241262411624106240562404624036240262401624006236162360623556235462353623526235162350623456234462343623426234162340623356233462333623326233162330623256232462323623226232162320623156231462313623126231162310623056230462303623026230162300622616226062255622546225362252622516225062245622446224362242622416224062235622346223362232622316223062225622246222362222622216222062215622146221362212622116221062205622046220362202622016220062161621606215562154621536215262151621506214562144621436214262141621406213562134621336213262131621306212562124621236212262121621206211562114621136211262111621106210562104621036210262101621006206162060620556205462053620526205162050620456204462043620426204162040620356203462033620326203162030620256202462023620226202162020620156201462013620126201162010620056200462003620026200162000616156161461613616126161161610616056160461603616026160161600615606155561554615536155261551615506154561544615436154261541615406153561534615336153261531615306152561524615236152261521615206151561514615136151261511615106150561504615036150261501615006146061455614546145361452614516145061445614446144361442614416144061435614346143361432614316143061425614246142361422614216142061415614146141361412614116141061405614046140361402614016140061360613556135461353613526135161350613456134461343613426134161340613356133461333613326133161330613256132461323613226132161320613156131461313613126131161310613056130461303613026130161300612606125561254612536125261251612506124561244612436124261241612406123561234612336123261231612306122561224612236122261221612206121561214612136121261211612106120561204612036120261201612006116061155611546115361152611516115061145611446114361142611416114061135611346113361132611316113061125611246112361122611216112061115611146111361112611116111061105611046110361102611016110061060610556105461053610526105161050610456104461043610426104161040610356103461033610326103161030610256102461023610226102161020610156101461013610126101161010610056100461003610026100161000606056060460603606026060160600605556055460553605526055160550605456054460543605426054160540605356053460533605326053160530605256052460523605226052160520605156051460513605126051160510605056050460503605026050160500604556045460453604526045160450604456044460443604426044160440604356043460433604326043160430604256042460423604226042160420604156041460413604126041160410604056040460403604026040160400603556035460353603526035160350603456034460343603426034160340603356033460333603326033160330603256032460323603226032160320603156031460313603126031160310603056030460303603026030160300602556025460253602526025160250602456024460243602426024160240602356023460233602326023160230602256022460223602226022160220602156021460213602126021160210602056020460203602026020160200601556015460153601526015160150601456014460143601426014160140601356013460133601326013160130601256012460123601226012160120601156011460113601126011160110601056010460103601026010160100600556005460053600526005160050600456004460043600426004160040600356003460033600326003160030600256002460023600226002160020600156001460013600126001160010600056000460003600026000160000555554555535555255551555505554455543555425554155540555345553355532555315553055524555235552255521555205551455513555125551155510555045550355502555015550055454554535545255451554505544455443554425544155440554345543355432554315543055424554235542255421554205541455413554125541155410554045540355402554015540055354553535535255351553505534455343553425534155340553345533355332553315533055324553235532255321553205531455313553125531155310553045530355302553015530055254552535525255251552505524455243552425524155240552345523355232552315523055224552235522255221552205521455213552125521155210552045520355202552015520055154551535515255151551505514455143551425514155140551345513355132551315513055124551235512255121551205511455113551125511155110551045510355102551015510055054550535505255051550505504455043550425504155040550345503355032550315503055024550235502255021550205501455013550125501155010550045500355002550015500054544545435454254541545405453454533545325453154530545245452354522545215452054514545135451254511545105450454503545025450154500544535445254451544505444454443544425444154440544345443354432544315443054424544235442254421544205441454413544125441154410544045440354402544015440054353543525435154350543445434354342543415434054334543335433254331543305432454323543225432154320543145431354312543115431054304543035430254301543005425354252542515425054244542435424254241542405423454233542325423154230542245422354222542215422054214542135421254211542105420454203542025420154200541535415254151541505414454143541425414154140541345413354132541315413054124541235412254121541205411454113541125411154110541045410354102541015410054053540525405154050540445404354042540415404054034540335403254031540305402454023540225402154020540145401354012540115401054004540035400254001540005353453533535325353153530535245352353522535215352053514535135351253511535105350453503535025350153500534525345153450534445344353442534415344053434534335343253431534305342453423534225342153420534145341353412534115341053404534035340253401534005335253351533505334453343533425334153340533345333353332533315333053324533235332253321533205331453313533125331153310533045330353302533015330053252532515325053244532435324253241532405323453233532325323153230532245322353222532215322053214532135321253211532105320453203532025320153200531525315153150531445314353142531415314053134531335313253131531305312453123531225312153120531145311353112531115311053104531035310253101531005305253051530505304453043530425304153040530345303353032530315303053024530235302253021530205301453013530125301153010530045300353002530015300052524525235252252521525205251452513525125251152510525045250352502525015250052451524505244452443524425244152440524345243352432524315243052424524235242252421524205241452413524125241152410524045240352402524015240052351523505234452343523425234152340523345233352332523315233052324523235232252321523205231452313523125231152310523045230352302523015230052251522505224452243522425224152240522345223352232522315223052224522235222252221522205221452213522125221152210522045220352202522015220052151521505214452143521425214152140521345213352132521315213052124521235212252121521205211452113521125211152110521045210352102521015210052051520505204452043520425204152040520345203352032520315203052024520235202252021520205201452013520125201152010520045200352002520015200051514515135151251511515105150451503515025150151500514505144451443514425144151440514345143351432514315143051424514235142251421514205141451413514125141151410514045140351402514015140051350513445134351342513415134051334513335133251331513305132451323513225132151320513145131351312513115131051304513035130251301513005125051244512435124251241512405123451233512325123151230512245122351222512215122051214512135121251211512105120451203512025120151200511505114451143511425114151140511345113351132511315113051124511235112251121511205111451113511125111151110511045110351102511015110051050510445104351042510415104051034510335103251031510305102451023510225102151020510145101351012510115101051004510035100251001510005050450503505025050150500504445044350442504415044050434504335043250431504305042450423504225042150420504145041350412504115041050404504035040250401504005034450343503425034150340503345033350332503315033050324503235032250321503205031450313503125031150310503045030350302503015030050244502435024250241502405023450233502325023150230502245022350222502215022050214502135021250211502105020450203502025020150200501445014350142501415014050134501335013250131501305012450123501225012150120501145011350112501115011050104501035010250101501005004450043500425004150040500345003350032500315003050024500235002250021500205001450013500125001150010500045000350002500015000044444344442444414444044433444324443144430444234442244421444204441344412444114441044403444024440144400443434434244341443404433344332443314433044323443224432144320443134431244311443104430344302443014430044243442424424144240442334423244231442304422344222442214422044213442124421144210442034420244201442004414344142441414414044133441324413144130441234412244121441204411344112441114411044103441024410144100440434404244041440404403344032440314403044023440224402144020440134401244011440104400344002440014400043433434324343143430434234342243421434204341343412434114341043403434024340143400433424334143340433334333243331433304332343322433214332043313433124331143310433034330243301433004324243241432404323343232432314323043223432224322143220432134321243211432104320343202432014320043142431414314043133431324313143130431234312243121431204311343112431114311043103431024310143100430424304143040430334303243031430304302343022430214302043013430124301143010430034300243001430004242342422424214242042413424124241142410424034240242401424004234142340423334233242331423304232342322423214232042313423124231142310423034230242301423004224142240422334223242231422304222342222422214222042213422124221142210422034220242201422004214142140421334213242131421304212342122421214212042113421124211142110421034210242101421004204142040420334203242031420304202342022420214202042013420124201142010420034200242001420004141341412414114141041403414024140141400413404133341332413314133041323413224132141320413134131241311413104130341302413014130041240412334123241231412304122341222412214122041213412124121141210412034120241201412004114041133411324113141130411234112241121411204111341112411114111041103411024110141100410404103341032410314103041023410224102141020410134101241011410104100341002410014100040403404024040140400403334033240331403304032340322403214032040313403124031140310403034030240301403004023340232402314023040223402224022140220402134021240211402104020340202402014020040133401324013140130401234012240121401204011340112401114011040103401024010140100400334003240031400304002340022400214002040013400124001140010400034000240001400003333323333133330333223332133320333123331133310333023330133300332323323133230332223322133220332123321133210332023320133200331323313133130331223312133120331123311133110331023310133100330323303133030330223302133020330123301133010330023300133000323223232132320323123231132310323023230132300322313223032222322213222032212322113221032202322013220032131321303212232121321203211232111321103210232101321003203132030320223202132020320123201132010320023200132000313123131131310313023130131300312303122231221312203121231211312103120231201312003113031122311213112031112311113111031102311013110031030310223102131020310123101131010310023100131000303023030130300302223022130220302123021130210302023020130200301223012130120301123011130110301023010130100300223002130020300123001130010300023000130000222221222202221122210222012220022121221202211122110221012210022021220202201122010220012200021211212102120121200211202111121110211012110021020210112101021001210002020120200201112011020101201002001120010200012000011111011100110101100010100100000
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
The key string for a length of 3 is givven below
009998997996995994993992991990988987986985984983982981980978977976975974973972971970968967966965964963962961960958957956955954953952951950948947946945944943942941940938937936935934933932931930928927926925924923922921920918917916915914913912911910908907906905904903902901900888788688588488388288188087787687587487387287187086786686586486386286186085785685585485385285185084784684584484384284184083783683583483383283183082782682582482382282182081781681581481381281181080780680580480380280180077767757747737727717707667657647637627617607567557547537527517507467457447437427417407367357347337327317307267257247237227217207167157147137127117107067057047037027017006665664663662661660655654653652651650645644643642641640635634633632631630625624623622621620615614613612611610605604603602601600555455355255155054454354254154053453353253153052452352252152051451351251151050450350250150044434424414404334324314304234224214204134124114104034024014003332331330322321320312311310302301300222122021121020120011101000
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;
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;
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.
Polynomial hashing, rolling hash (kinda like Rabin-Karp string matching algorithm) should do the trick for (i).
Keep a counter and set it to 0
- pc June 03, 2015Assume you have a string or char array of secret password
Read the number from input keypad
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
Does this answer the question?