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 \leq n \leq 500; 1 \leq s \leq 10^4; 1 \leq c_i \leq 10^4; 1 \leq m_i \leq 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 \geq 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