I tried to think of ways to solve this problem, after not being able to think of a solution which I could reason about, I read the editorial and understood the binary search solution, but I don't understand why the greedy solution works.

Could someone help reason about the greedy solution?

Yesterday I read in cpalgorithm that if we are given a prime modulus, $$$p$$$, which is of the form $$$p = c \cdot 2^{k} + 1$$$, then, assuming $$$g$$$ is a primitive root of the prime $$$p$$$, then, exponentiating $$$g$$$, we can obtain congruences of numbers comprime to $$$p$$$, $$$g^{k} \equiv a \pmod{p}$$$ where $$$gcd(a, m) = 1$$$. As, this $$$g$$$ produces congruences of all numbers less than $$$p$$$ which are coprime to $$$p$$$, it obviously has $$$z$$$, such that $$$g^{z} \equiv 1 \pmod{p}$$$, $$$z = \varphi(p) = c \cdot 2^{k}$$$. If $$$c = 1$$$, then, if $$$\omega_{2^{k}}$$$ is the $$$2^{k}$$$-th root of unity modulo $$$p$$$. we can use $$$(\omega_{2^{k}}^{2})^{2^{k - 1}} = \omega_{2^{k}}^{2^{k}} = 1$$$ which means $$$\omega_{2^{k}}^{2} = \omega_{2^{k - 1}}$$$ and we can obtain answer. If $$$c \neq 1$$$, $$$c \equiv 1 \pmod{p}$$$ and you had two polynomials, both of degree $$$n$$$ where $$$n$$$ is a power of 2, $$$2n \leq 2^{k}$$$ and you wanted to get the convolution of the two polynomials, how would you do it? Or if there is some other way, please do share.

If I have said anything wrong, please correct me.

UPD: After reading again, I realize that $$$g^{c}$$$ is the $$$2^{k}$$$th root of unity as the period is $$$c \cdot 2^{k}$$$ ending with $$$1$$$, Sorry for asking this stupid question.