<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

137. Funny Strings

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Let's consider a string of non-negative integers, containing N elements. Suppose these elements are S1 S2 .. SN, in the order in which they are placed inside the string. Such a string is called 'funny' if the string S1+1 S2 S3 .. SN-1 SN -1 can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings 2 2 2 3 and 1 2 1 2 2 are funny, but the string 1 2 1 2 is not. Your task is to find a funny string having N elements, for which the sum of its elements (S1+S2+..+SN) is equal to K.


Input

The input contains two integers: N (2<=N<=1000) and K (1<=K<=30000). Moreover, GCD(N,K)=1 (it can be proven that this is a necessary condition for a string to be funny).


Output

You should output one line containing the elements of the funny string found. These integers should be separated by blanks.

Hint

GCD(A,B) = the greatest common divisor of A and B.
The 'funny' strings are also named Euclid strings in several papers.


Sample Input

9 16
Sample Output

1 2 2 2 1 2 2 2 2
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

<|response|>
1. Abridged Problem Statement  
Given two integers N (2 ≤ N ≤ 1000) and K (1 ≤ K ≤ 30000) with gcd(N, K)=1, construct an array S of length N of non‐negative integers summing to K such that if we form S′ by  
  – S′₁ = S₁+1  
  – S′ᵢ = Sᵢ for 2≤i≤N−1  
  – S′ₙ = Sₙ−1  
then S′ is a cyclic rotation of S. Output any such S.

2. Key Observations  
- Let a = ⌊K/N⌋ and d = K mod N.  We can start with all Sᵢ = a and then distribute d extra “+1” units.  
- gcd(N,K)=1 implies gcd(N,d)=1, so d has a multiplicative inverse modulo N.  
- We need to choose a rotation shift t (1≤t<N) so that adding 1 at position 1 and subtracting 1 at position N corresponds exactly to rotating S by t positions.  
- Algebraically, one shows that we must have  
    d·t ≡ −1 (mod N)  ⇔ d·t ≡ N−1 (mod N).  
- Once t is known, distributing the d extra units along the cycle x→(x+t) mod N, starting from x=0, will align the +1 and −1 after a t‐shift.

3. Full Solution Approach  
1. Read N, K.  
2. Compute  
   a = K / N  (integer division)  
   d = K % N  
3. Initialize an array ans of length N with all entries = a.  
4. Find t in [1..N−1] such that (d * t) % N == N−1.  Since gcd(d,N)=1, exactly one such t exists.  
5. Distribute the d extra ones:  
   x = 0  
   repeat  
      x = (x + t) % N  
      ans[x]++  
   until x == N−1  (you will have made exactly d increments)  
6. Print ans[0], ans[1], …, ans[N−1] separated by spaces.

Time complexity is O(N²) if we search t by brute force, but N≤1000 makes this perfectly fine.

4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, k;

void read() { cin >> n >> k; }

void solve() {
    /*
     * A funny (Euclid) string of length n with sum k is the discretized line
     * y = (k/n) x: every term is either floor(k/n) or that plus one. Start with
     * all terms equal to a = k/n; d = k % n of them must be bumped by one. Find
     * the step t (1 <= t < n) with t*d == -1 (mod n), then walk positions
     * x = t, 2t, ... mod n incrementing each until reaching index n-1; those d
     * positions form the staircase pattern that makes the string funny.
     */

    int a = k / n;
    int d = k % n;

    vector<int> ans(n, a);

    for(int t = 1; t < n; t++) {
        if(t * d % n == n - 1) {
            int x = 0;
            do {
                x = (x + t) % n;
                ans[x]++;
            } while(x != n - 1);
            break;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def main():
    data = sys.stdin.read().split()
    N, K = map(int, data)

    # Base value for each position and remainder
    a = K // N
    d = K % N

    # Initialize answer array
    ans = [a] * N

    # Find t with d * t ≡ N-1 (mod N)
    t = None
    for candidate in range(1, N):
        if (d * candidate) % N == N - 1:
            t = candidate
            break

    # Distribute the d extra ones
    x = 0
    while True:
        x = (x + t) % N
        ans[x] += 1
        if x == N - 1:
            break

    # Print the array
    print(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()
```