SP17779 CHARCHOC - Charlie and the Chocolate Factory

Charlie and the Chocolate Factory Charlie Bucket is a loving and kind boy, who lives in poverty with his mother, father and four bedridden grandparents. Down the street, there is Willy Wonka’s chocolate factory who is famous for both his chocolates and the factory. After long years of conducting business with chocolate, now Wonka finally decided to make an heir to the factory. So, instead of putting golden tickets in ordinary Wonka bars (which is old fashioned….:P) he decided to take a programming contest to choose 5 candidates for the heir. And, then he will give a tough problem to them (among these five) and the first to answer will be the winner. After taking the contest Wonka eventually gets his five candidates and Charlie is one of them.Now, before throwing the heir deciding problem towards them he decided to give them 2 hints. 1st hint is an algorithm whose pseudo code is given below  ``` # `array` is 1-indexed def MakeNewArray(array, d): if d == 1: return array else: array = MakeNewArray(array, d-1) new_array = [array[array[i]] for i in 1..inf] return new_array ``` For example, if array = \[2, 3, 5, 7, 11, ...\], then MakeNewArray(array, 2) = \[3, 5, 11, ...\]. 2nd hint is **Kuddus** array. A **Kuddus** array is a sorted array of **Kuddus** numbers. **Kuddus** numbers are such **prime** numbers which can be expressed as the summation of squares of two distinct positive integers.For, example 5 can be expressed as 1 $ ^{2} $ +2 $ ^{2} $ . So it is a **Kuddus** number. Also 13(3 $ ^{2} $ +2 $ ^{2} $ ) and 17(4 $ ^{2} $ +1 $ ^{2} $ ) are **Kuddus** number. So, first few numbers of **Kuddus** array are 5,13,17…. etc. Now, it’s time for the heir deciding problem. The problem is as follows. There are **n** boxes and all of them are initially empty(no chocolate). Now in every step (starts from 1st step to the last) Wonka will do some sets of operation. The operation are of four kinds. The operation is indicated by an integer **op**. i) If **op=1**. Then it is an add operation and it is followed by two integers **a,b**. It means Wonka will add **b** chocolates in box number **a**. ii) If **op=2**. Then it is a multiplication operation which is also followed by two integers **a,b**. It means Wonka will multiply the number of chocolates in box number **a** by **b**. iii) If **op=3**. Then it is a swap operation which is also followed by **a,b**. It means the boxes **a** and **b** will exchange their chocolates. iv) If **op=4**. Then it is a clear operation which is followed by only a single integer **a**. This means Wonka will remove all chocolates from box **a**. There are **2** sets of operation. One is an **ordinary** set and another is **special** set. In normal steps he will perform the **ordinary** set of operation serially (as it appears in the input). And in the special steps he will perform the **special** set of operation serially. Special step number is stored in an array called **Special** array. More precisely, he has an array named **Special** of infinite numbers. It is a sorted array. The elements of the array are denoted by **Special\[1\],Special\[2\],Special\[3\]**....etc \[normal array system\].So he will perform the special operation only at **Special\[1\]th,Special\[2\]th, Special\[3\]th**…... etc steps. Now, **Special:=MakeNewArray(Kuddus,d).** Here **MakeNewArray** and **Kuddus** are described previously. **d** is an integer which will be given in the input. At last Wonka will tell the number of steps **s**. Now, Charlie is busy in some other works. So, he needs your help. You will have to answer after **s** steps what is the total number of chocolates in all the boxes (summation of all the chocolates in every box). **Input:** Input consists of some test cases (not more than **15**). Every case begins with two integer **n (>=2)** and **d (1

N/A

N/A