Problem: There is a string s, consisting of capital Latin letters. Let's denote its current length as |s|. During one move it is allowed to apply one of the following operations to it: 

  * INSERT pos ch — insert a letter ch in the string s in the position pos (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z). The letter ch becomes the pos-th symbol of the string s, at that the letters shift aside and the length of the string increases by 1. 
  * DELETE pos — delete a character number pos (1 ≤ pos ≤ |s|) from the string s. At that the letters shift together and the length of the string decreases by 1. 
  * REPLACE pos ch — the letter in the position pos of the line s is replaced by ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z). At that the length of the string does not change. 



Your task is to find in which minimal number of moves one can get a t string from an s string. You should also find the sequence of actions leading to the required results.

Input

The first line contains s, the second line contains t. The lines consist only of capital Latin letters, their lengths are positive numbers from 1 to 1000.

Output

In the first line print the number of moves k in the given sequence of operations. The number should be the minimal possible one. Then print k lines containing one operation each. Print the operations in the format, described above. If there are several solutions, print any of them.

Examples

Input

ABA
ABBBA


Output

2
INSERT 3 B
INSERT 4 B


Input

ACCEPTED
WRONGANSWER


Output

10
REPLACE 1 W
REPLACE 2 R
REPLACE 3 O
REPLACE 4 N
REPLACE 5 G
REPLACE 6 A
INSERT 7 N
INSERT 8 S
INSERT 9 W
REPLACE 11 R

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
class StopWatch {
 public:
  StopWatch(const char*) {}
  StopWatch() {}
};
inline void DoNothing() {}
template <typename T>
inline T Abs(const T a) {
  return a < 0 ? -a : a;
}
template <typename T>
inline T Min(const T a, const T b) {
  return a < b ? a : b;
}
template <typename T>
inline T Max(const T a, const T b) {
  return a > b ? a : b;
}
static const double eps = 1.0e-8;
inline double IsEqual(const double a, const double b) {
  return Abs(a - b) < eps;
}
inline double IsGreater(const double a, const double b) { return a > b + eps; }
inline double IsLess(const double a, const double b) { return a + eps < b; }
struct Rand {
  unsigned long z_, w_;
  unsigned long get32() {
    z_ = 36969 * (z_ & 65535) + (z_ >> 16);
    w_ = 18000 * (w_ & 65535) + (w_ >> 16);
    return (z_ << 16) + (w_ & 65535);
  }
  void Reset() {
    z_ = 1;
    w_ = 1;
  }
  Rand() { Reset(); }
};
struct Operation {
  enum EOpType { OP_INSERT, OP_DELETE, OP_REPLACE, OP_NOTHNING };
  EOpType opType;
  size_t pos;
  char ch;
  Operation() : opType(OP_NOTHNING) {}
  Operation(const EOpType opType_, const size_t pos_, const char ch_)
      : opType(opType_), pos(pos_), ch(ch_) {}
  static Operation CreateInsert(const size_t pos, const char ch) {
    return Operation(OP_INSERT, pos, ch);
  }
  static Operation CreateDelete(const size_t pos) {
    return Operation(OP_DELETE, pos, ' ');
  }
  static Operation CreateReplace(const size_t pos, const char ch) {
    return Operation(OP_REPLACE, pos, ch);
  }
  static Operation CreateNothing() { return Operation(OP_NOTHNING, 0, ' '); }
  std::ostream& put(std::ostream& os) const {
    switch (opType) {
      case OP_INSERT:
        os << "INSERT " << pos + 1 << ' ' << ch;
        break;
      case OP_DELETE:
        os << "DELETE " << pos + 1;
        break;
      case OP_REPLACE:
        os << "REPLACE " << pos + 1 << ' ' << ch;
        break;
    }
    return os;
  }
  void Apply(std::string& str) const {
    switch (opType) {
      case OP_INSERT:
        str.insert(pos, 1, ch);
        break;
      case OP_DELETE:
        str.erase(pos, 1);
        break;
      case OP_REPLACE:
        str[pos] = ch;
        break;
    }
  }
};
std::ostream& operator<<(std::ostream& os, const Operation& op) {
  return op.put(os);
}
struct DataField {
  bool bFullyCalculated;
  bool bValid;
  size_t bestOpCount;
  Operation bestOperation;
  DataField() : bFullyCalculated(false), bValid(false), bestOpCount(0) {}
  void TryToSetOperation(const Operation& operation, const size_t opCount) {
    if (!bValid || opCount < bestOpCount) {
      bValid = true;
      bestOpCount = opCount;
      bestOperation = operation;
    }
  }
};
struct DataField2 {
  bool bFullyCalculated;
  bool bValid;
  size_t bestOpCount;
  Operation::EOpType bestOperation;
  DataField2() : bFullyCalculated(false), bValid(false), bestOpCount(0) {}
  void TryToSetOperation(const Operation::EOpType& operation,
                         const size_t opCount) {
    if (!bValid || opCount < bestOpCount) {
      bValid = true;
      bestOpCount = opCount;
      bestOperation = operation;
    }
  }
};
template <typename T>
std::vector<std::vector<T> > CreateVector2d(const size_t rowCnt,
                                            const size_t colCnt) {
  std::vector<std::vector<T> > result;
  for (size_t row = 0; row < rowCnt; ++row) {
    result.push_back(std::vector<T>(colCnt));
  }
  return result;
}
std::vector<Operation> FindAnswerNoRec1(const std::string& strSrc,
                                        const std::string strDst) {
  const size_t sizeSrc = strSrc.size();
  const size_t sizeDst = strDst.size();
  std::vector<std::vector<DataField> > data =
      CreateVector2d<DataField>(sizeSrc + 1, sizeDst + 1);
  data[0][0].bValid = true;
  data[0][0].bestOpCount = 0;
  for (size_t subSrcLen = 0; subSrcLen <= sizeSrc; ++subSrcLen) {
    for (size_t subDstLen = 0; subDstLen <= sizeDst; ++subDstLen) {
      if (subDstLen > 0 && subSrcLen > 0) {
        const size_t prevOpCnt = data[subSrcLen - 1][subDstLen - 1].bestOpCount;
        const bool bReplaceIsNeeded =
            (strSrc[subSrcLen - 1] != strDst[subDstLen - 1]);
        if (bReplaceIsNeeded) {
          data[subSrcLen][subDstLen].TryToSetOperation(
              Operation::CreateReplace(subDstLen - 1, strDst[subDstLen - 1]),
              prevOpCnt + 1);
        } else {
          data[subSrcLen][subDstLen].TryToSetOperation(
              Operation::CreateNothing(), prevOpCnt);
        }
      }
      if (subSrcLen > 0) {
        const size_t prevOpCnt = data[subSrcLen - 1][subDstLen].bestOpCount;
        data[subSrcLen][subDstLen].TryToSetOperation(
            Operation::CreateDelete(subDstLen), prevOpCnt + 1);
      }
      if (subDstLen > 0) {
        const size_t prevOpCnt = data[subSrcLen][subDstLen - 1].bestOpCount;
        data[subSrcLen][subDstLen].TryToSetOperation(
            Operation::CreateInsert(subDstLen - 1, strDst[subDstLen - 1]),
            prevOpCnt + 1);
      }
    }
  }
  std::vector<Operation> ans;
  size_t idxSrc = sizeSrc;
  size_t idxDst = sizeDst;
  while (idxSrc != 0 || idxDst != 0) {
    const DataField& dataField = data[idxSrc][idxDst];
    switch (dataField.bestOperation.opType) {
      case Operation::OP_DELETE:
        ans.push_back(dataField.bestOperation);
        idxSrc--;
        break;
      case Operation::OP_INSERT:
        ans.push_back(dataField.bestOperation);
        idxDst--;
        break;
      case Operation::OP_REPLACE:
        ans.push_back(dataField.bestOperation);
        idxDst--;
        idxSrc--;
        break;
      case Operation::OP_NOTHNING:
        idxDst--;
        idxSrc--;
        break;
    }
  }
  std::reverse(ans.begin(), ans.end());
  return ans;
}
std::vector<Operation> FindAnswerNoRec2(const std::string& strSrc,
                                        const std::string strDst) {
  const size_t sizeSrc = strSrc.size();
  const size_t sizeDst = strDst.size();
  std::vector<std::vector<DataField2> > data =
      CreateVector2d<DataField2>(sizeSrc + 1, sizeDst + 1);
  data[0][0].bValid = true;
  data[0][0].bestOpCount = 0;
  for (size_t subSrcLen = 0; subSrcLen <= sizeSrc; ++subSrcLen) {
    for (size_t subDstLen = 0; subDstLen <= sizeDst; ++subDstLen) {
      if (subDstLen > 0 && subSrcLen > 0) {
        const size_t prevOpCnt = data[subSrcLen - 1][subDstLen - 1].bestOpCount;
        const bool bReplaceIsNeeded =
            (strSrc[subSrcLen - 1] != strDst[subDstLen - 1]);
        if (bReplaceIsNeeded) {
          data[subSrcLen][subDstLen].TryToSetOperation(Operation::OP_REPLACE,
                                                       prevOpCnt + 1);
        } else {
          data[subSrcLen][subDstLen].TryToSetOperation(Operation::OP_NOTHNING,
                                                       prevOpCnt);
        }
      }
      if (subSrcLen > 0) {
        const size_t prevOpCnt = data[subSrcLen - 1][subDstLen].bestOpCount;
        data[subSrcLen][subDstLen].TryToSetOperation(Operation::OP_DELETE,
                                                     prevOpCnt + 1);
      }
      if (subDstLen > 0) {
        const size_t prevOpCnt = data[subSrcLen][subDstLen - 1].bestOpCount;
        data[subSrcLen][subDstLen].TryToSetOperation(Operation::OP_INSERT,
                                                     prevOpCnt + 1);
      }
    }
  }
  std::vector<Operation> ans;
  size_t idxSrc = sizeSrc;
  size_t idxDst = sizeDst;
  while (idxSrc != 0 || idxDst != 0) {
    const DataField2& dataField = data[idxSrc][idxDst];
    switch (dataField.bestOperation) {
      case Operation::OP_DELETE:
        ans.push_back(Operation::CreateDelete(idxDst));
        idxSrc--;
        break;
      case Operation::OP_INSERT:
        ans.push_back(Operation::CreateInsert(idxDst - 1, strDst[idxDst - 1]));
        idxDst--;
        break;
      case Operation::OP_REPLACE:
        ans.push_back(Operation::CreateReplace(idxDst - 1, strDst[idxDst - 1]));
        idxDst--;
        idxSrc--;
        break;
      case Operation::OP_NOTHNING:
        idxDst--;
        idxSrc--;
        break;
    }
  }
  std::reverse(ans.begin(), ans.end());
  return ans;
}
bool CheckAnswer(const std::string& strSrc, const std::string& strDst,
                 const std::vector<Operation>& ans) {
  std::string strRes(strSrc);
  for (size_t i = 0; i < ans.size(); ++i) {
    ans[i].Apply(strRes);
  }
  std::cout << "strSrc = " << strSrc << std::endl;
  std::cout << "strDst = " << strDst << std::endl;
  std::cout << "strRes = " << strRes << std::endl;
  const bool bEq = strDst == strRes;
  std::cout << (bEq ? "OK" : "NOT ok") << std::endl;
  return bEq;
}
bool Solve(bool bCheckInputStream = false) {
  std::string strSrc, strDst;
  std::cin >> strSrc >> strDst;
  if (bCheckInputStream && !std::cin) {
    return false;
  }
  StopWatch _sw;
  const std::vector<Operation> ans = FindAnswerNoRec2(strSrc, strDst);
  std::cout << ans.size() << std::endl;
  for (size_t i = 0; i < ans.size(); ++i) {
    std::cout << ans[i] << std::endl;
  }
  return true;
}
int main() { Solve(); }