Strun nəzəriyyəsi#10639
Strun nəzəriyyəsi, bir çox fizik tərəfindən ən perspektivli və populyar nəzəriyyələrdən biri hesab edilir. Bu nəzəriyyəyə görə, kainat müxtəlif ölçülərdən ibarətdir və ən böyük ölçü 11-ci ölçüdür. 11 ölçüdən kənarda kainat qeyri-sabit olur və 11-dən çox olan ölçülər 11-ölçülü kainata yığılır. İndi qarşınızda strun nəzəriyyəsinin nəzəri problemini modelləşdirmək vəzifəsi durur.
Sistemimizdə n strun var, bunlar 1-dən n-ə qədər nömrələnmişdir və OTP Dekart müstəvisində S = i üçün i = 1, ..., n sətirlərində yerləşdirilmişdir, burada OT zaman çərçivələrini, OS isə hissəciklərin cari strununu təmsil edir. Hissəciklər yalnız gələcəyə doğru hərəkət edir və bəlkə də strunlar arasında tullanaraq enerji sərf edirlər. Əvvəlcə yalnız hissəciklər enerji itirmədən sakit vəziyyətdə qala bilər, yəni (t, p) vəziyyətindən (t + 1, p) vəziyyətinə keçid 0 enerji tələb edir və sistemimizdə başqa keçidlər (hələlik) nəzərdə tutulmayıb. Qeyd edək ki, sistemimiz keçmişə səyahəti dəstəkləmir (və ya keçmişə keçidin dəyərinin sonsuz olduğunu qəbul edir). Sizin əsas məqsədiniz hissəciyin s[1] strunundan t[1] zaman intervalında s[2] strununa t[2] zaman intervalında keçməsi üçün tələb olunan minimal enerji miqdarını hesablamaq və ya bunun mümkün olmadığını deməkdir.
İndi müəyyən xarici qüvvələri təsvir edəcəyik: teleportlar və massiv obyektlər. Teleport t zaman intervalında enerji xərcləri ilə (a[1], ..., a[n-1]) meydana gəldikdə, hər hansı bir hissəcik (t, i) vəziyyətində dərhal (t, i + 1) vəziyyətinə a[i] enerji itkisi ilə və ya (t, i - 1) vəziyyətinə a[i-1] enerji itkisi ilə keçə bilər (əgər i + 1 və ya i - 1 strunu varsa). Əgər t zaman intervalında (b[1], ..., b[n]) enerjiləri ilə massiv obyekt əlavə etsək, bu, t və t + 1 arasında keçidə təsir edəcək, belə ki, i strununda olan hissəcik eyni strunda qalmaq üçün b[i] enerji xərci tələb edəcək (əks halda hissəcik məkan-zamanda yox olacaq). Beləliklə, yerinə yetirməli olduğunuz 3 növ sorğu var:
1 t a[1], ..., a[n-1] - t zamanında a[i] enerjiləri ilə teleport əlavə edin;
2 t b[1], ..., b[n] - t zamanında b[i] enerjiləri ilə massiv obyekt əlavə edin;
3 t[1] s[1] t[2] s[2] - biz (t[1], s[1]) → (t[2], s[2]) vəziyyətləri arasında səyahət edən hissəciklə qarşılaşırıq, bu hissəcik üçün minimal enerji miqdarı nə qədər olmalıdır?
Qeyd edək ki, əgər eyni zaman dövründə 2 teleport / massiv obyekt əlavə etmək təklif olunursa, daha sonrakı əvvəlkini əvəz edir.
Birinci sətirdə sistemimizdəki strunların sayı n və sorğuların sayı q göstərilir (1 ≤ n ≤ 11, 1 ≤ q ≤ 10^4).
Növbəti q sətirdə, şərtdə təsvir olunan formatda sorğuların təsviri verilir, məhdudiyyətlərlə:
0 ≤ a[i], b[i] ≤ 100 - enerji xərcləri;
1 ≤ t ≤ 5 * 10^4, 1 ≤ t[1] ≤ t[2] ≤ 5 * 10^4 - zaman çərçivələri;
1 ≤ s[1], s[2] ≤ n - strunların mövqeyi.
Üçüncü tip hər bir sorğu üçün tək bir ədəd - ona cavab verin.
Nümunə 1