In AtCoder City, types of garbage are collected regularly. The -th type of garbage is collected on days when the date modulo equals . N i (i=1,2,…,N) q i ​

r i ​

Answer queries. In the -th query , given that the -th type of garbage is put out on day , answer the next day on which it will be collected. Q j (j=1,2,…,Q) t j ​

d j ​

Here, if the -th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day. i