 # WA in ALATE

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
long long t,i,x,x1,x2,n,q,a,b,div,j,k=0,sum;
long long ans=(long long)malloc(sizeof(long long)*1000005);
scanf("%lld",&t);
while(t–)
{
scanf("%lld %lld",&n,&q);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(i=1;i<=n;i++)
{
j=i;
b[i]=0;
while(j<=n)
{
b[i]=(b[i]%1000000007+(a[j]*a[j]))%1000000007;
j+=i;
}
}
while(q–)
{
scanf("%lld",&x);
if(x==2)
{
scanf("%lld %lld",&x1,&x2);
for(i=1;i<=sqrt(x1);i++)
if(x1%i==0)
{
b[i]=(b[i]%1000000007-(a[x1]a[x1])+1000000007)%1000000007;
b[i]=(b[i]%1000000007+(x2
x2))%1000000007;
div=x1/i;
if(div!=i)
{
b[div]=(b[div]%1000000007-(a[x1]a[x1])+1000000007)%1000000007;
b[div]=(b[div]%1000000007+(x2
x2))%1000000007;
}
}
a[x1]=x2;
}
else
{
scanf("%lld",&x1);
ans[k++]=b[x1]%1000000007;
}
}
}
i=k;
k=0;
while(k<i)
{
printf("%lld\n",ans[k]);
k++;
}
return 0;
}

Not sure where actually it’s going wrong… But looks like it’s overflowing somewhere… I wrote this random python testCaseGenerator and checked it against AC solution and found your solution is giving -ve answer somewhere in middle…

``````import random
t = 10
print t
numLimit = 1000000000
numLowLimit = 1
nLimit = 100000
qLimit = 100000
for _ in range(t):
n = random.randint(1,nLimit)
q = random.randint(1,qLimit)
print n,q
for __ in range(n-1):
print random.randint(numLowLimit,numLimit),
print random.randint(numLowLimit,numLimit)
for __ in range(q):
qType = random.randint(1,2)
if qType == 1:
print 1,random.randint(1,n)
else:
print 2,random.randint(1,n),random.randint(numLowLimit,numLimit)
``````

While taking diff it was showing this in terminal… From where I claimed above statement…

``````-523114558 Your code output
---
476885449 Actual Output

110701c110701 Some Line Number