An được mời tham gia trò chơi "Siêu thị may mắn" do đài truyền hình ZTV tổ chức. Siêu thi được đặt trong trường quay truyền hình có $n$ mặt hàng được đánh số từ $1$ đến $n$ và mặt hàng thứ $i$ được niêm yết giá là $c_i$ đồng. Theo thể lệ trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là $s$ đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thi với điều kiện mặt hàng thứ $i$ chỉ được mua với số lượng nhiều nhất là $m_i$. An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.

Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n,s,c[i],m[i] ($1\le n\le 500;1\le s\le {10}^4;1\le c_i\le {10}^4;1\le m_i\le 100$)

Input:

• Dòng đầu ghi hai số $s,n$

• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số $c_i,m_i$

Output:

• Dòng đầu ghi $d$ là phần dư của tổng số cách mua hàng chia cho $131131$

• Nếu $d\ge 1$ thì dòng thứ hai ghi một cách mua hàng tìm được là một dãy gồm $n$ số nguyên, trong đó số hạng thứ $i$ là số lượng mặt hàng thứ $i$ mua được trong cách mua này.

Ví dụ:

INPUT

12 3
4 1
6 2
2 1

OUTPUT

2
0 2 0