queryOnPrimes2

Ông Sáu là người yêu những số nguyên tố, và ông cũng muốn con trai mình cũng phải sành sỏi về số nguyên tố. Ông giao cho con trai mình nhiệm vụ như sau:

Ông xét 1000 số nguyên tố đầu tiên, ký hiệu là chuỗi p[1..1000], p[i] là số nguyên tố thứ i. Cho hai số L và R, (L <= R) ông định nghĩa giá trị hàm s(L, R) là:

Tuy nhiên ông không muốn con trai mình phải thực hiện lại việc tính toán này quá nhiều lần mỗi khi ông hỏi về bộ giá trị (L,R) , ông muốn con trai mình tính sẵn 1000 số nguyên tố đầu tiên để lưu lại. Sau đó ông sẽ cho danh sách nhiều truy vấn liên tiếp gồm các cặp  (L,R) như trên, ông yêu cầu con trai trả lời giá trị s(L, R). Tuy nhiên vì lo sợ con trai mình tính số lớn nhiều quá, ông chỉ cần kết quả lấy dư khi chia cho 10^9+9

Ví dụ:

• Với L = [2], R = [2], thì kết quả queryOnPrimes(L, R) = [9]. Các số nguyên tố đầu tiên là p = [2 3 5 7 11 13]. Ta có p(L) = 3, p(R) = 3 kết quả là s(L,R) = 3^2 = 9
• Với L = [5], R = [6], thì kết quả queryOnPrimes(L, R) = [290]. Ta có p(L) = 11, p(R) = 13, nên s(L,R) = 11^2+13^2 = 290

Đầu ra:

• [Thời gian chạy] 0.5 giây với C++, 3 giây với Java và C#, 4 giây vs Python và Js
• [Đầu vào] array.integer lQueries, rQueries
  1 <= lQueries[i] <= rQueries[i] <= 1000 : các cặp truy vấn (L,R)
1 <= lQueries.size() == rQueries.size() <= 100
• [Đầu ra] array.integer
  Kết quả cho từng truy vấn theo thứ tự của mảng queries, lấy dư khi chia cho 10^9+9