Ağac

Sergi işini bitirdikdən sonra sevimli məşğuliyyəti olan rəsm çəkməyə qərar verdi. İlk olaraq, o, Baş Ujland Ağacını təsvir etdi. Bu ağac özünəməxsusdur: 1-dən n-ə qədər nömrələnmiş və dövrü şəkildə yerləşdirilmiş n budaqdan ibarətdir. Birinci budağın ardınca ikinci, ikinci budağın ardınca üçüncü və s. gəlir, n nömrəli budaqdan sonra isə yenidən birinci budaq gəlir.

Başlanğıcda hər bir budaqda müəyyən sayda quş var (bəzən heç quş olmaya da bilər). Ağacda ümumilikdə m quş var və bu quşlar 1-dən m-ə qədər nömrələnmişdir. Hər bir quşun çəkisi belə müəyyən edilir: i nömrəli quşun çəkisi (a[i] + b) mod (10^9 + 7) bərabərdir, burada a və b sabitlərdir. x mod y ifadəsi x-in y-ə bölünməsindən qalan qalığı göstərir. Bütün quşların çəkiləri fərqlidir. Məlumdur ki, i nömrəli budaqda başlanğıcda c[i] quş var. Belə ki, 1 nömrəli budaqda 1, 2, .., c[1] nömrəli quşlar, 2 nömrəli budaqda c[1] + 1, c[1] + 2, ..., c[1] + c[2] nömrəli quşlar və s. yerləşir. c[1] + c[2] + ... + c[n] = m təmin edilir.

Hər saniyə belə bir proses baş verir: hər bir budaqdan, üzərində ən azı bir quş olan, ən kiçik çəkili quş növbəti budağa uçur. Məsələn, əgər ağac 3 budaqdan ibarətdirsə və birincidə {1, 3, 5} çəkili quşlar, ikincidə {2, 7}, üçüncüdə isə {4, 5, 6} çəkili quşlar varsa, bir saniyə sonra budaqlardakı quşların çəkiləri müvafiq olaraq {3, 4, 5}, {1, 7}, {2, 5, 6} olacaq. Sergi iki rəqəm düşündü: k və t. İndi o maraqlanır: t saniyədə k nömrəli budaqdan uçacaq quşun çəkisi nə olacaq?

Vəzifə

Ağacdakı quşların yerləşməsi haqqında məlumat və k və t rəqəmləri verilmişdir. t saniyədə k nömrəli budaqdan uçacaq quşun çəkisini müəyyən edən proqram yazın.

Giriş məlumatları

Giriş faylının ilk sətirində altı tam ədəd n m k t a b (1 ⩽ n ⩽ 10^4, 1 ⩽ m ⩽ 2 • 10^6, 1 ⩽ k ⩽ n, 1 ⩽ t ⩽ 10^9, 1 ⩽ a < 10^9 + 7, 0 ⩽ b < 10^9 + 7) — ağacın budaqlarının sayı, ağacdakı quşların sayı, Serginin düşündüyü rəqəmlər və quşun çəkisini müəyyən edən sabitlər verilmişdir.

İkinci sətirdə n tam ədəd c[1], c[2], ..., c[n] (0 ⩽ c[i] ⩽ m), burada c[i] — i nömrəli budaqda başlanğıcda olan quşların sayıdır. Bütün quşların çəkiləri cüt-cüt fərqlidir və c[1] + c[2] + ... + c[n] = m olduğu təmin edilir.

Çıxış məlumatları

Çıxış faylı tree.out-a bir tam ədəd yazın — t saniyədə k nömrəli budaqdan uçacaq quşun çəkisi, ya da −1, əgər t saniyədən əvvəl bu budaqda heç bir quş olmayacaqsa.

Nümunələr

Qiymətləndirmə

Altvəzifə Ballar Əlavə məhdudiyyətlər Tələb olunan altvəzifələr

0 0 Şərtdəki testlər -

1 17 1 ⩽ n,m,t ⩽ 100 0

2 12 1 ⩽ n ⩽ 100, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 5000 0, 1

3 18 1 ⩽ n ⩽ 100, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 109 0, 1, 2

4 24 1 ⩽ n ⩽ 10^4, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 109 0, 1, 2, 3

5 29 Əlavə məhdudiyyətlər yoxdur 0, 1, 2, 3, 4