dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])  // j ≥ v[i]
dp[i][j] = dp[i-1][j]                               // j < v[i]

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;        // n: 物品数量, m: 背包容量
int v[N], w[N];  // v: 体积, w: 价值
int dp[N][N];    // dp[i][j]

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      dp[i][j] = dp[i - 1][j];  // 默认不选第i个物品
      if (j >= v[i]) {          // 如果能装下，尝试选择
        dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
      }
    }
  }

  printf("%d\n", dp[n][m]);
  return 0;
}

dp[j] = max(dp[j], dp[j-v[i]] + w[i])

#include <iostream>
using namespace std;

const int N = 1010;
int dp[N];
int v[N], w[N];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {  // 注意：倒序遍历
      dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  cout << dp[m] << endl;
  return 0;
}

dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])  // j ≥ v[i]
dp[i][j] = dp[i-1][j]                               // j < v[i]

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N][N];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      dp[i][j] = dp[i - 1][j];  // 不选第i个物品
      if (j >= v[i]) {
        // 选第i个物品，注意这里是 dp[i][...] 而不是 dp[i-1][...]
        dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
      }
    }
  }

  printf("%d\n", dp[n][m]);
  return 0;
}

#include <iostream>
using namespace std;

const int N = 1010;
int dp[N];
int v[N], w[N];

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d", &v[i], &w[i]); }
  for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {  // 注意：正序遍历
      dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  cout << dp[m] << endl;
  return 0;
}

dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k); // 0 <= k <= s[i]

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      // 枚举第i个物品选k件
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
      }
    }
  }

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int dp[N][N];  // 使用二维DP演示

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d%d", &v[i], &w[i], &s[i]); }

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      // 枚举第i个物品选k件
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
      }
    }
  }

  printf("%d\n", dp[n][m]);
  return 0;
}

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int dp[N];  // 使用一维DP演示

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) { scanf("%d%d%d", &v[i], &w[i], &s[i]); }

  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {
      // 枚举第i个物品选k件
      for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
        dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
      }
    }
  }

  printf("%d\n", dp[m]);
  return 0;
}

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 12010;  // n*log(s)
const int M = 2010;
int cnt = 0;  // 每种物品拆分后，一共形成的组数，最后就是01背包问题
int v[N], w[N];
int n, m;
int dp[M];  //  01背包的一维优化

int main() {
  scanf("%d%d", &n, &m);

  for (int i = 1; i <= n; i++) {
    int vx, wx, s;
    scanf("%d%d%d", &vx, &wx, &s);
    int k = 1;
    while (k <= s) {  // 这里是 k <= s
      cnt++;          // 总组数+1
      v[cnt] = vx * k;
      w[cnt] = wx * k;

      s -= k;
      k *= 2;
    }
    // 如果s按照 1 2 4 8 …… 拆分后还剩下，就直接加入到里面
    if (s > 0) {
      cnt++;  // 总组数+1
      v[cnt] = vx * s;
      w[cnt] = wx * s;
    }
  }
  n = cnt;  // 拆分后相当于现在有cnt个物品了，然后决定每个物品选还是不选

  // 把所有的物品都拆分了，放入到了v[],
  // w[]中，下面就可以用01背包来遍历实现最大值了
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); }
  }

  printf("%d\n", dp[m]);
  return 0;
}

dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k])

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N];  // v[i][j] 表示第i组第j个物品
int s[N];
int f[N];  // f[j] 表示容量为j的情况下的最大值

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s[i]);
    for (int j = 1; j <= s[i]; j++) { scanf("%d%d", &v[i][j], &w[i][j]); }
  }

  for (int i = 1; i <= n; i++)           // 循环分组
    for (int j = m; j >= 0; j--) {       // 注意体积从大到小枚举！！01背包
      for (int k = 1; k <= s[i]; k++) {  // 每个分组内部选择第k个物品
        if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
      }
    }
  cout << f[m];
  return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 510;
const int INF = 1e9;
int a[N][N], f[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= i; j++) 
            scanf("%d", &a[i][j]);
    
    // 初始化，防止边界问题
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++) 
            f[i][j] = -INF;
    
    // DP开始
    f[1][1] = a[1][1];
    // 从上往下递推
    for(int i = 2; i <= n; i++) 
        for(int j = 1; j <= i; j++) 
        {
            f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
        }
    
    // 找出最后一行的最大值
    int res = -INF;
    for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 5e3 + 5;
int nums[N], dp[N];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", nums + i); }
  // 初始化
  fill(dp, dp + N, 1);
  int res = 1;
  // 动态规划
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; }
    }
    res = max(res, dp[i]);
  }
  printf("%d", res);
  return 0;
}

#include <cstdio>
#include <iostream>
using namespace std;
/*
  功能：求一个序列的最长严格递增子序列（LIS）的长度
  算法：贪心 + 二分（O(n log n)）
*/
const int N = 1e5 + 5;
int a[N], tails[N];
int main() {
  int n;
  scanf("%d", &n);
  // 输入数组
  for (int i = 0; i < n; i++) { scanf("%d", &a[i]); }
  // 初始化
  int len = 1;      // 当前最长递增子序列长度
  tails[0] = a[0];  // tails[i] 表示长度为 i+1 的递增子序列的末尾最小值

  for (int i = 1; i < n; i++) {
    // 如果当前数比 tails[len-1] 还大，说明可以直接扩展LIS
    if (a[i] > tails[len - 1]) {
      tails[len++] = a[i];
    } else {
      // 否则，用二分查找“第一个 >= a[i]”的tails位置替换
      int l = 0, r = len - 1;
      while (l < r) {
        int mid = l + (r - l) / 2;
        if (tails[mid] >= a[i])
          r = mid;
        else
          l = mid + 1;
      }
      tails[l] = a[i];  // 更新该位置的最小值
    }
  }
  printf("%d\n", len);
  return 0;
}

// 假设 f[N][N] 已定义，A 和 B 字符串从下标1开始
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        if (A[i] == B[j]) {
            f[i][j] = f[i-1][j-1] + 1;
        } else {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
}
cout << f[n][m];

dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1

for (int i = 1; i <= m; i++) dp[i][0] = i;
for (int j = 1; j <= n; j++) dp[0][j] = j;

#include <iostream>
using namespace std;

const int N = 2e3 + 5;
int dp[N][N];

int main() {
  string s1, s2;
  cin >> s1 >> s2;

  int m = s1.length(), n = s2.length();

  // 初始化
  for (int i = 1; i <= m; i++) dp[i][0] = i;
  for (int j = 1; j <= n; j++) dp[0][j] = j;

  // 状态转移
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (s1[i - 1] == s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = min(
            dp[i - 1][j] + 1,                      // 删除
            min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1) // 插入 / 替换
        );
      }
    }
  }

  printf("%d", dp[m][n]);
  return 0;
}

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 310;
const int INF = 0x3f3f3f3f;
int a[N], s[N];  // s[i]是前i堆石子的前缀和
int f[N][N];     // f[i][j] 表示的是从第i堆合并到第j堆，最小代价
int n;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

  // 计算合并的前缀和
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

  // 初始化, 区间长度为1时
  for (int i = 1; i <= n; i++) f[i][i] = 0;

  // 要按照区间从小到大得到 f[1][n],直接从2开始
  for (int len = 2; len <= n; len++)  // k表示枚举区间的长度
  {
    for (int i = 1; i + len - 1 <= n; i++)  // 枚举区间的左端点
    {
      int l = i, r = i + len - 1;  // 枚举左右端点
      f[l][r] = INF;
      for (int k = l; k < r; k++) {
        f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
      }
    }
  }
  printf("%d\n", f[1][n]);
  return 0;
}

// 写法1：完全背包  二维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
// f[i][j]表示从前i个数中选，总和恰好为j的划分方法的方案数
int f[N][N], n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i <= n; ++i) f[i][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (j >= i)
        f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
      else
        f[i][j] = f[i - 1][j] % mod;
    }
  }

  printf("%d\n", f[n][n]);
  return 0;
}

// 完全背包，一维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], n;

int main() {
  scanf("%d", &n);
  f[0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j) f[j] = (f[j] + f[j - i]) % mod;

  printf("%d\n", f[n]);
  return 0;
}

f[i][j] = f[i-1][j-1] + f[i-j][j]

// 计数dp
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N], n;  // f[i][j]表示 总和是i，并且由j个数组成的方案数

int main() {
  scanf("%d", &n);
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i)    // 枚举总和i  让总和从1枚举到n
    for (int j = 1; j <= i; ++j)  // 枚举整数的个数  从1枚举到n个数
      f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

  int ans = 0;
  for (int i = 1; i <= n; ++i) ans = (ans + f[n][i]) % mod;
  printf("%d\n", ans);

  return 0;
}

#include <cmath>
#include <cstring>
#include <iostream>
typedef long long LL;
using namespace std;
LL dgt(LL n) {  // 计算整数n有多少位
  LL res = 0;
  while (n) ++res, n /= 10;
  return res;
}
LL cnt(LL n, int i) {  // 计算从1到n的整数中数字i出现多少次
  LL res = 0, d = dgt(n);
  for (LL j = 1; j <= d; ++j) {  // 从右到左第j位上数字i出现多少次
    // l和r是第j位左边和右边的整数 (视频中的abc和efg); dj是第j位的数字
    LL p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10;
    // 计算第j位左边的整数小于l (视频中xxx = 000 ~ abc - 1)的情况
    if (i) res += l * p;
    if (!i && l)
      res += (l - 1) * p;  // 如果i = 0, 左边高位不能全为0 (视频中xxx = 001 ~ abc - 1)
    // 计算第j位左边的整数等于l (视频中xxx = abc)的情况
    if ((dj > i) && (i || l)) res += p;
    if ((dj == i) && (i || l)) res += r + 1;
  }
  return res;
}
int main() {
  LL a, b;
  scanf("%lld%lld", &a, &b);
  if (a > b) swap(a, b);
  for (int i = 0; i <= 9; ++i) { printf("%lld ", cnt(b, i) - cnt(a - 1, i)); }
  return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int base[10];
int f[10][10];
int g[10][10];

void init() {
  base[0] = 1;
  for (int i = 1; i <= 9; i++) base[i] = base[i - 1] * 10;

  // 从00……0 - 99……9 的各位数字有多少个，其中i为数字个数（包含前导零）
  for (int i = 0; i <= 9; i++) f[1][i] = 1;
  for (int i = 2; i <= 9; i++)
    for (int j = 0; j <= 9; j++) f[i][j] = f[i - 1][j] * 10 + base[i - 1];

  // 从1 - 99……9 的各位数字有多少个，其中i为数字个数（不包含前导零）
  for (int i = 1; i <= 9; i++) g[1][i] = 1;  // 循环从1开始
  for (int i = 2; i <= 9; i++) {
    g[i][0] = g[i - 1][0] + f[i - 1][0] * 9;
    for (int j = 1; j <= 9; j++)
      g[i][j] = g[i - 1][j] + f[i - 1][j] * 9 + base[i - 1];
  }
}

vector<int> dp(int n) {
  vector<int> ans(10, 0);  // 记录答案
  if (n <= 0) return ans;  // 边界条件

  vector<int> nums;
  while (n) nums.push_back(n % 10), n /= 10;

  vector<int> last(10, 0);  // 记录前缀中各个数字个数

  // 统计1 - 99……9(n-1个9)里面各个数字有多少个
  for (int i = 0; i <= 9; i++) ans[i] = g[nums.size() - 1][i];
  // 统计大于10……0(n-1个0) 的树里各个数字有多少个
  for (int i = nums.size() - 1; i >= 0; i--) {
    // 循环变量i可以表示剩下的数字有多少个
    int x = nums[i];
    for (int j = i == nums.size() - 1; j < x; j++) {  // 第一次循环不能有0
      // 前缀部分
      for (int k = 0; k <= 9; k++) ans[k] += last[k] * base[i];
      // 当前位置部分
      ans[j] += base[i];
      // 后缀部分
      for (int k = 0; k <= 9; k++) ans[k] += f[i][k];
    }
    // 更新前缀计数器
    last[x]++;

    // 统计叶子节点（这个数本身）
    if (!i)
      for (int k = 0; k <= 9; k++) ans[k] += last[k];
  }
  return ans;
}

vector<int> ask(int a, int b) {
  auto x = dp(b);
  auto y = dp(a - 1);
  vector<int> ans;
  for (int i = 0; i <= 9; i++) ans.push_back(x[i] - y[i]);
  return ans;
}

void print(vector<int> ans) {
  for (auto x : ans) printf("%d ", x);
  puts("");
}

bool check(int x) {
  auto t = ask(x, x);
  vector<int> cnt(10, 0);
  while (x) cnt[x % 10]++, x /= 10;
  for (int i = 0; i <= 9; i++)
    if (cnt[i] != t[i]) return false;
  return true;
}

int main() {
  init();

  // 这里是一个DEBUG函数
  //  for(int i = 1 ; i <= 1000000 ; i*=10) {
  //      if(!check(i))
  //          printf("ERROR:%d\n",i);
  //  }

  int a, b;
  while (cin >> a >> b, a || b) {
    if (a > b) swap(a, b);
    auto t = ask(a, b);
    print(t);
  }

  return 0;
}