Մրցույթ

Ռոբերտը և Դավիթը պատրաստել են n հատ խնդիր, որոնց որոշ մասը պետք է օգտագործվի R&D կոչվող մրցույթում։ Խնդիրները համարակալված են 1-ից n թվերով։ Ամեն խնդիր լուծվում է որոշակի ալգորիթմի միջոցով․ i-րդ խնդիրը լուծվում է ai համարի ալգորիթմով (ալգորիթմները նույնպես համարակալված են)։ Մրցույթում օգտագործվող խնդիրների վերջնական ընտրությունը կայացնում է R&D մրցույթի տնօրեն Ալեքսանդրը, ում կազմված խնդիրներից ոչ մեկը դուր չի գալիս։

q օրերի ընթացքում տեղի են ունենում երկու տեսակի իրադարձություններ․

1 l r y. Ռոբերտը և Դավիթը փոխարինում են l-ից r համարներով խնդիրները y ալգորիթմով լուծվող խնդիրներով։ Ֆորմալ ai:=y:

2 l r. Ռոբերտը և Դավիթը Ալեքսանդրին են ներկայացնում l-ից r համարներով խնդիրները, իսկ Ալեքսանդրը ընտրում է [l,r] հատվածի [l1,r1] ենթահատված (l ≤ l1 ≤ r1 ≤ r), որը պարունակում է մինիմալ քանակությամբ խնդիրներ, բայց պարունակում է [l,r] հատվածում առկա ալգորիթմներից յուրաքանչյուրով լուծվող գոնե մեկ խնդիր։ Ֆորմալ գոյություն չունի այնպիսի i, որ l ≤ i ≤ r և ai ≠ aj կամայական j-ի համար, որտեղ l1 ≤ j ≤ r1:

Յուրաքանչյուր 2-րդ տեսակի հարցման համար անհրաժեշտ է արտածել Ալեքսանդրի ընտրած ենթահատվածի երկարությունը։

Մուտքային տվյալներ

Առաջին տողում տրված է մեկ բնական թիվ n(1 ≤ n ≤ 100000)։ Հաջորդ տողում տրված են n թվեր․ a հաջորդականություն (ai ≤ 10)։ Հաջորդ տողում տրված է q(1 ≤ q ≤ 100000) թիվը: Հաջորդ q տողերից յուրաքանչուրում տրված է հերթական հարցման նկարագրությունը․ 1 l r y, կամ 2 l r տեսքի (1 ≤ l ≤ r ≤ n y ≤ 10)։

Ելքային տվյալներ

Յուրաքանչյուր 2-րդ տեսակի հարցման համար անհրաժեշտ է արտածել Ալեքսանդրի ընտրած ենթահատվածի երկարությունը։

Օրինակներ

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) Օրինակները,

• Ենթախնդիր 1 (10 միավոր) n, q ≤ 100,

• Ենթախնդիր 2 (11 միավոր) n, q ≤ 4000,

• Ենթախնդիր 3 (12 միավոր) ai, y ≤ 2,

• Ենթախնդիր 4 (22 միավոր) 1ին տեսակի հարցումներ չկան,

• Ենթախնդիր 5 (15 միավոր) 1ին տեսակի հարցումներում l = r

• Ենթախնդիր 6 (17 միավոր) ai, y ≤ 5

• Ենթախնդիր 7 (13 միավոր) լրացուցիչ սահմանափակումներ չկան