#include <stdio.h>
#include <iostream>
#include <string.h>
#include <vector>
#define N 1000000
using namespace std ;
int sieve[ 1000001 ] ;
int array[ 100001 ] ;
struct node{
int value ;
bool flag ; // flag = 1 ; if all the element in the range which each internal node represent are 1
} ;
struct node ST[ 400002 ] ;
void primes ( ) {
sieve[ 1 ] = 1 ;
sieve[ 2 ] = 2 ;
sieve[ 0 ] = 1 ;
for ( int i = 4 ; i <= N; i + = 2 )
sieve[ i] = 2 ;
for ( int i = 3 ; i * i <= N; i + = 2 )
if ( ! sieve[ i] ) {
sieve[ i] = i;
for ( int j = i * i; j <= N; j + = 2 * i)
if ( ! sieve[ j] ) // ensure not to overwrite already filled entries
sieve[ j] = i;
}
for ( int i = 3 ; i <= N; i + = 2 ) // Only prime numbers are left which are filled with 0's
if ( ! sieve[ i] )
sieve[ i] = i ;
}
void make( int low, int high, int pos) {
if ( low == high) {
ST[ pos] .value = sieve[ array[ low] ] ; // building Segment Tree on LeastPrimeDivisor of Ai's
if ( array[ low] == 1 )
ST[ pos] .flag = 1 ;
else
ST[ pos] .flag = 0 ;
return ;
}
int mid = ( low+ high) / 2 ;
make( low, mid, 2 * pos + 1 ) ;
make( mid+ 1 , high, 2 * pos + 2 ) ;
ST[ pos] .value = max( ST[ 2 * pos+ 1 ] .value , ST[ 2 * pos+ 2 ] .value ) ;
ST[ pos] .flag = 0 ;
return ;
}
void update( int L, int R, int low, int high, int pos) {
if ( low > R || high < L)
return ;
if ( ST[ pos] .flag ) // Return if the leaf nodes in the subtree rooted at node 'pos' contains all 1's, no update is needed
return ;
if ( low == high) { // leaf node
array[ low] / = sieve[ array[ low] ] ; // change ST[pos].value and array[low] value accordingly
ST[ pos] .value = sieve[ array[ low] ] ;
if ( array[ low] == 1 )
ST[ pos] .flag = 1 ;
return ;
}
int mid = ( low+ high) / 2 ;
if ( mid >= R)
update( L, R, low, mid, 2 * pos+ 1 ) ;
else if ( mid < L)
update( L, R, mid+ 1 , high, 2 * pos+ 2 ) ;
else {
update( L, R, low, mid, 2 * pos+ 1 ) ;
update( L, R, mid+ 1 , high, 2 * pos+ 2 ) ;
}
ST[ pos] .value = max( ST[ 2 * pos + 1 ] .value , ST[ 2 * pos + 2 ] .value ) ;
if ( ST[ 2 * pos + 1 ] .flag && ST[ 2 * pos + 2 ] .flag ) // put the flag = 1 for node 'pos', if flag of both child of the node, i.e, left.flag and right.flag, both are 1
ST[ pos] .flag = 1 ;
return ;
}
int query( int L, int R, int low, int high, int pos) { //Simple query function
if ( low > R || high < L)
return - 1 ;
if ( L <= low && high <= R)
return ST[ pos] .value ;
int mid = ( low+ high) / 2 ;
return max( query( L, R, low, mid, 2 * pos+ 1 ) , query( L, R, mid+ 1 , high, 2 * pos+ 2 ) ) ;
}
int main( ) {
primes( ) ;
int n, m, t, q, L, R ;
ios_base:: sync_with_stdio ( false ) ; cin .tie ( 0 ) ;
scanf ( "%d" , & t) ;
while ( t-- ) {
scanf ( "%d %d" , & n, & m) ;
memset ( array, 0 , sizeof ( array) ) ;
memset ( & ST, 0 , sizeof ( ST) ) ;
for ( int i = 0 ; i < n; i++ )
scanf ( "%d" , & array[ i] ) ;
make( 0 , n- 1 , 0 ) ; // building segment on 'array'
for ( int i = 0 ; i < m ; i++ ) {
scanf ( "%d %d %d" , & q, & L, & R) ;
L-- ; // 0 based indexed
R-- ;
L = min( L, R) ; // Asserting L <= R, not neccessary if input is well behaved
R = max( L, R) ;
if ( ! q)
update( L, R, 0 , n- 1 , 0 ) ;
else
printf ( "%d " , query( L, R, 0 , n- 1 , 0 ) ) ;
}
printf ( "\n " ) ;
}
return 0 ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8dmVjdG9yPgoKI2RlZmluZSBOIDEwMDAwMDAKCnVzaW5nIG5hbWVzcGFjZSBzdGQgOwoKaW50IHNpZXZlWzEwMDAwMDFdCTsKaW50IGFycmF5WzEwMDAwMV0JOwoKc3RydWN0IG5vZGV7CgoJaW50IHZhbHVlCTsKCWJvb2wgZmxhZwk7CQkJCQkJLy8gZmxhZyA9IDEgOyBpZiBhbGwgdGhlIGVsZW1lbnQgaW4gdGhlIHJhbmdlIHdoaWNoIGVhY2ggaW50ZXJuYWwgbm9kZSByZXByZXNlbnQgYXJlIDEgCgp9OwoKc3RydWN0IG5vZGUgU1RbNDAwMDAyXQk7Cgp2b2lkIHByaW1lcyAoKXsKCglzaWV2ZVsxXSA9IDEJOwoJc2lldmVbMl0gPSAyCTsKCXNpZXZlWzBdID0gMQk7CgoJZm9yKGludCBpID0gNDsgaSA8PSBOOyBpICs9IDIpCgkJc2lldmVbaV0gPSAyCTsKCglmb3IgKGludCBpID0gMzsgaSAqIGkgPD0gTjsgaSArPSAyKQoKCQlpZiAoIXNpZXZlW2ldKXsKCgkJCXNpZXZlW2ldID0gaTsKCQkJZm9yIChpbnQgaiA9IGkgKiBpOyBqIDw9IE47IGogKz0gMiAqIGkpCgkJCQlpZighc2lldmVbal0pICAgCQkJCQkJLy8gZW5zdXJlIG5vdCB0byBvdmVyd3JpdGUgYWxyZWFkeSBmaWxsZWQgZW50cmllcwoJCQkJCXNpZXZlW2pdID0gaTsKCQl9CgogICAgZm9yIChpbnQgaSA9IDM7IGkgPD0gTjsgaSArPSAyKQkJCQkJCS8vIE9ubHkgcHJpbWUgbnVtYmVycyBhcmUgbGVmdCB3aGljaCBhcmUgZmlsbGVkIHdpdGggMCdzCiAgICAgICAgaWYgKCFzaWV2ZVtpXSkKICAgICAgICAgICAgc2lldmVbaV0gPSBpICAgIDsKIH0KCnZvaWQgbWFrZShpbnQgbG93LCBpbnQgaGlnaCwgaW50IHBvcyl7CgoJaWYgKGxvdyA9PSBoaWdoKXsKCgkJU1RbcG9zXS52YWx1ZSA9IHNpZXZlW2FycmF5W2xvd11dCTsJCQkvLyBidWlsZGluZyBTZWdtZW50IFRyZWUgb24gTGVhc3RQcmltZURpdmlzb3Igb2YgQWkncwoJCQoJCWlmIChhcnJheVtsb3ddID09IDEpCgkJCVNUW3Bvc10uZmxhZyA9IDEJOwoJCWVsc2UKCQkJU1RbcG9zXS5mbGFnID0gMAk7CgoJCXJldHVybiA7Cgl9CgoJaW50IG1pZCA9IChsb3craGlnaCkgLyAyCTsKCW1ha2UobG93LCBtaWQsIDIqcG9zICsgMSkJOwoJbWFrZShtaWQrMSwgaGlnaCwgMipwb3MgKyAyKTsKCVNUW3Bvc10udmFsdWUgPSBtYXgoU1RbMipwb3MrMV0udmFsdWUsIFNUWzIqcG9zKzJdLnZhbHVlKQk7CglTVFtwb3NdLmZsYWcgPSAwCTsKCglyZXR1cm4JOwoKfQoKdm9pZCB1cGRhdGUoaW50IEwsIGludCBSLCBpbnQgbG93LCBpbnQgaGlnaCwgaW50IHBvcyl7CgoJaWYgKGxvdyA+IFIgfHwgaGlnaCA8IEwpCgkJcmV0dXJuCTsKCglpZiAoU1RbcG9zXS5mbGFnKQkJCQkJCQkJCS8vIFJldHVybiBpZiB0aGUgbGVhZiBub2RlcyBpbiB0aGUgc3VidHJlZSByb290ZWQgYXQgbm9kZSAncG9zJyBjb250YWlucyBhbGwgMSdzLCBubyB1cGRhdGUgaXMgbmVlZGVkCgkJcmV0dXJuIAk7CgoJaWYgKGxvdyA9PSBoaWdoKXsJCQkJCQkJCQkvLyBsZWFmIG5vZGUKCgkJYXJyYXlbbG93XSAvPSBzaWV2ZVthcnJheVtsb3ddXQk7CQkJCQkJLy8gY2hhbmdlIFNUW3Bvc10udmFsdWUgYW5kIGFycmF5W2xvd10gdmFsdWUgYWNjb3JkaW5nbHkKCQlTVFtwb3NdLnZhbHVlID0gc2lldmVbYXJyYXlbbG93XV0JOwoJCWlmIChhcnJheVtsb3ddID09IDEpCgkJCVNUW3Bvc10uZmxhZyA9IDEJOwoJCXJldHVybgk7Cgl9CgoJaW50IG1pZCA9IChsb3craGlnaCkgLwkyCTsKCglpZiAobWlkID49IFIpCgkJdXBkYXRlKEwsIFIsIGxvdywgbWlkLCAyKnBvcysxKQk7CgkKCWVsc2UgaWYgKG1pZCA8IEwpCgkJdXBkYXRlKEwsIFIsIG1pZCsxLCBoaWdoLCAyKnBvcysyKQk7CgkKCWVsc2V7CgoJCXVwZGF0ZShMLCBSLCBsb3csIG1pZCwgMipwb3MrMSkJOwoJCXVwZGF0ZShMLCBSLCBtaWQrMSwgaGlnaCwgMipwb3MrMikJOwoKCX0KCglTVFtwb3NdLnZhbHVlID0gbWF4KFNUWzIqcG9zICsgMV0udmFsdWUsIFNUWzIqcG9zICsgMl0udmFsdWUpCTsKCglpZiAoU1RbMipwb3MgKyAxXS5mbGFnICYmIFNUWzIqcG9zICsgMl0uZmxhZykJCQkJCQkJLy8gcHV0IHRoZSBmbGFnID0gMSBmb3Igbm9kZSAncG9zJywgaWYgZmxhZyBvZiBib3RoIGNoaWxkIG9mIHRoZSBub2RlLCBpLmUsIGxlZnQuZmxhZyBhbmQgcmlnaHQuZmxhZywgYm90aCBhcmUgMSAKCQlTVFtwb3NdLmZsYWcgPSAxCTsKCglyZXR1cm4JOwkKfQoKaW50IHF1ZXJ5KGludCBMLCBpbnQgUiwgaW50IGxvdywgaW50IGhpZ2gsIGludCBwb3MpewkJCQkJLy9TaW1wbGUgcXVlcnkgZnVuY3Rpb24KCglpZiAobG93ID4gUiB8fCBoaWdoIDwgTCkKCQlyZXR1cm4gLTEJOwoKCWlmIChMIDw9IGxvdyAmJiBoaWdoIDw9IFIpCgkJcmV0dXJuIFNUW3Bvc10udmFsdWUJOwoKCWludCBtaWQgPSAobG93K2hpZ2gpIC8gMgk7CglyZXR1cm4gbWF4KHF1ZXJ5KEwsIFIsIGxvdywgbWlkLCAyKnBvcysxKSwgcXVlcnkoTCwgUiwgbWlkKzEsIGhpZ2gsIDIqcG9zKzIpKQk7Cgp9CgppbnQgbWFpbigpewoKCXByaW1lcygpCTsKCWludCBuLCBtLCB0LCBxLCBMLCBSIDsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyAgIGNpbi50aWUoMCkgIDsKCXNjYW5mKCIlZCIsICZ0KSAJOwoJd2hpbGUodC0tKXsKCgkJc2NhbmYoIiVkICVkIiwgJm4sICZtKQk7CgkJbWVtc2V0KGFycmF5LCAwLCBzaXplb2YoYXJyYXkpKQk7CgkJbWVtc2V0KCZTVCwgMCwgc2l6ZW9mKFNUKSkJOwoKCQlmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCQkJCXNjYW5mKCIlZCIsICZhcnJheVtpXSkJOwoJCQoJCW1ha2UoMCwgbi0xLCAwKQk7CQkJCQkvLyBidWlsZGluZyBzZWdtZW50IG9uICdhcnJheScgCgoJCWZvciAoaW50IGkgPSAwOyBpIDwgbSA7IGkrKyl7CgkJCXNjYW5mKCIlZCAlZCAlZCIsICZxLCAmTCwgJlIpCTsKCgkJCUwtLTsJCS8vIDAgYmFzZWQgaW5kZXhlZAoJCQlSLS07CgoJCQlMID0gbWluKEwsIFIpCTsJCQkvLyBBc3NlcnRpbmcgTCA8PSBSLCBub3QgbmVjY2Vzc2FyeSBpZiBpbnB1dCBpcyB3ZWxsIGJlaGF2ZWQKCQkJUiA9IG1heChMLCBSKQk7CgoJCQlpZiAoIXEpCgoJCQkJdXBkYXRlKEwsIFIsIDAsIG4tMSwgMCkJOwoKCQkJZWxzZQoJCQkJCgkJCQlwcmludGYoIiVkICIsIHF1ZXJ5KEwsIFIsIDAsIG4tMSwgMCkpCTsKCQl9CgkJcHJpbnRmKCJcbiIpCTsKCX0KCglyZXR1cm4gMAk7Cn0=