1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def rozwiazanie(ilosc_zolnierzy, ilosc_rozkazow, rozkazy):
    MOD = 2
    dp = [[0] * (ilosc_zolnierzy + 1) for _ in range(2)]
    dp[0][0] = 1

    for rozkaz in rozkazy:
        a, b = rozkaz
        a -= 1
        b -= 1
        dp_nastepne = [[0] * (ilosc_zolnierzy + 1) for _ in range(2)]

        for j in range(ilosc_zolnierzy + 1):
            if dp[0][j]:
                if a < j or b < j:
                    dp_nastepne[0][j] = (dp_nastepne[0][j] + dp[0][j]) % MOD
                else:
                    dp_nastepne[1][j] = (dp_nastepne[1][j] + dp[0][j]) % MOD

            if dp[1][j] and j < ilosc_zolnierzy:
                dp_nastepne[1][j + 1] = (dp_nastepne[1][j + 1] + dp[1][j]) % MOD

        dp = dp_nastepne

    wynik = [(dp[0][j] + dp[1][j]) % MOD for j in range(ilosc_zolnierzy + 1)]
    return wynik[1:]

ilosc_zolnierzy, ilosc_rozkazow = map(int, input().split())
rozkazy = [list(map(int, input().split())) for _ in range(ilosc_rozkazow)]
print(*rozwiazanie(ilosc_zolnierzy, ilosc_rozkazow, rozkazy))