Beshiiiiiii Kore Father Timm Memorial Prog...
Limits 1s, 512 MB

One day at group-”NDC TOP 100” of Notre Dame College, the ICT teacher gave the a students' a task by forming Q teams. He wrote N numbers in the board in a single line and called them array W. After that to each team, he gave five variables (l,r,p,m,k)(l, r, p, m, k).

Let, index jj be a point of division of the numbers from ll to rr i.e, lj<rl \le j < r

Let, X=GXP([Wl...Wj],p)GXP([Wj+1...Wr],p)X = \frac{GXP([W_{l}...W_{j}], p)}{GXP([W_{j+1}...W_{r}], p)}

Now he asked them if it was possible to find an index jj such that XmkX \ge m^k. If there are multiple solutions then find an index jj such that it minimizes XmkX - m^k

Note: The GXP function of any array AA with a given range cc to dd and parameter pp is the multiplication of the all the numbers in that range raised to the power pp i.e,

GXP([AcAc+1Ad],p)=AcpAc+1p...AdpGXP([A_{c}A_{c+1}…A_{d}], p) = A_{c}^{p} * A_{c+1}^{p} * ... * A_{d}^{p}

Now there was a team which consist of two students naming Farhan Ishrak and Azmain Muksit. They were so called "Matbor" in their class. They wanted to solve all of the other teams' solutions along with their own to look cool. That being said, they collected every variable from the others. There was a problem though, they could not even solve their own. Thus they hired you to solve the problems on their behalf. Well, can you figure out the solution?


1<N1051 < N \le 10^5

0<Q,k,p1050 < Q, k, p \le 10^5

0<Wi,m1090 < W_i, m \le 10^9

0<l<rN0 < l < r \le N



W1  W2  ...  WNW_1\;W_2\;...\; W_N

l1  r1  p1  m1  k1l_1\; r_1\; p_1\; m_1\; k_1

l2  r2  p2  m2  k2l_2\; r_2\; p_2\; m_2\; k_2



lQ  rQ  pQ  mQ  kQl_Q\; r_Q\; p_Q\; m_Q\; k_Q


For each team, if the answer is Yes, then print YESYES followed by the valid index jj in a new line (see explanation of sample test case for better understanding), else print NONO.


Subtask 1 (for 1010 points):

  • 1<N1001 < N \le 100

  • 0<Q1000 < Q \le 100

  • 0<Wi,p100 < W_i, p \le 10

  • 0<mk10180 < m^k \le 10^{18}

Subtask 2 (for 3030 points): 1<N1001 < N \le 100

Subtask 3 (for 6060 points): General Constraints


5 2
3 5 7 5 2
1 5 2 5 2
1 4 2 5 4

For the first team, when j=3j=3, X=GXP([3,5,7],2)GXP([5,2],2)=3252725222=110.25X=\frac{GXP([3,5,7], 2)}{GXP([5,2], 2)}=\frac{3^2*5^2*7^2}{5^2*2^2}=110.25 and mk=25m^k=25 which meets the given condition and XmkX-m^k is minimized

For the second team, the highest possible value of XX that can be found is 441441 which is less than mk=625m^k=625


Login to submit.


33% Solution Ratio
user.828682Earliest, 3w ago
user.828682Fastest, 0.3s
user.828682Lightest, 5.7 MB
user.828682Shortest, 658B
Toph uses cookies. By continuing you agree to our Cookie Policy.