Make It

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK113/hindi/MKIT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK113/mandarin/MKIT.pdf), [Russian](http://www.codechef.com/download/translated/COOK113/russian/MKIT.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK113/vietnamese/MKIT.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK113/bengali/MKIT.pdf) as well. Roger is the mayor of a city with $N$ citizens (numbered $1$ through $N$). On each day, each citizen has to pay a tax; let's denote the tax paid by the $i$th citizen by $A_i$. One day, Roger was extremely bored, so he decided to start a returntaxforfun program. The program is simple: on each day, Roger picks some nonempty group of citizens and returns to them the taxes they paid that day. However, picking some random citizens is not very fun, and Roger has always been fond of the number $K$ and its multiples, so he decided to only pick groups of citizens such that the product of the taxes returned to them is a multiple of $K$. Among all such choices, he picks a group which minimises the sum of the returned taxes (he does not want to waste too much money). We know that Roger is a moody person. Sometimes, he chooses two integers $1 \le L \le R \le N$ and decides that he will not consider the citizens numbered $L$ through $R$ for the returntaxforfun program, i.e. the sum of returned taxes should be the smallest possible among all groups that do not contain any of these citizens. Roger told Melanie, his secretary, to do all the work and report to him the smallest sum of taxes that should be returned. Now, Melanie is looking for your help. You should answer $Q$ queries. In each query, you are given the integers $L$ and $R$ and you should compute the smallest sum of taxes that should be returned or determine that there is no way to choose a group of citizens such that the product of the taxes returned to them is a multiple of $K$. Note that the queries are independent — a citizen that is not considered for the returntaxforfun program in one query may be considered for the program again in subsequent queries. ### Input  The first line of the input contains three spaceseparated integers $N$, $Q$ and $K$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  $Q$ lines follow. Each of these lines contains two spaceseparated integers $L$ and $R$ describing a query. ### Output For each query, print a single line containing one integer — the smallest returned sum, or $1$ if it is impossible to pick a valid group of citizens. ### Constraints  $1 \le N, Q \le 10^5$  $1 \le K \le 10^8$  $1 \le A_i \le 10^8$ for each valid $i$  $1 \le L \le R \le N$ ### Example Input ``` 5 5 24 6 3 12 2 8 3 3 2 4 3 4 1 3 2 2 ``` ### Example Output ``` 11 14 11 1 14 ```Author:  kmaaszraa 
Editorial  https://discuss.codechef.com/problems/MKIT 
Tags  cook113, dynamicprogramming, kmaaszraa, kmaaszraa, medium 
Date Added:  17122019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 