Oyun "Bölünmə"

İki oyunçu X və Y aşağıdakı oyunu oynayırlar:

• Təbii ədəd p və A çoxluğu var, bu çoxluq n müxtəlif qeyri-mənfi tam ədədlərdən ibarətdir, A = {a[1], a[2], ..., a[n]}, burada hər bir a[i] p-dən kiçikdir.

• Oyunçular növbə ilə hərəkət edirlər. Hər bir oyunçu A çoxluğundan bir ədəd çıxarır.

• Əgər dəqiq k raunddan sonra A-da qalan ədədlərin cəmi p-yə bölünürsə, Oyunçu X qalib gəlir. Əks halda, Oyunçu Y qalib gəlir.

Hər iki oyunçu optimal oynayarsa, kimin qalib gələcəyini müəyyən edən proqram yazın.

Giriş məlumatları

Birinci sətir oyunların sayı t-ni ehtiva edir.

Sonra hər bir i = 0, 1, ..., t – 1 üçün:

• (3i + 2) nömrəli sətirdə n, k (1 ≤ k ≤ n ≤ 5000) və p (p ≤ 10^18) ədədləri yerləşir;

• (3i + 3) nömrəli sətirdə ya X, ya da Y simvolu yerləşir, bu simvol hansı oyunçunun birinci hərəkət etdiyini göstərir;

• (3i + 4) nömrəli sətirdə a[1], a[2], ..., a[n] (0 ≤ a[i] < p) ədədləri yerləşir.

Çıxış məlumatları

Bir sətirdə t simvolu (ayırıcı olmadan) çıxarın, hər bir test üçün bir simvol. i-ci simvol X olacaq, əgər X i-ci oyunda Y-nin oyunundan asılı olmayaraq qalib gəlirsə; əks halda Y simvolunu çıxarın.

Nümunələr