Как изменить подстроку в строку со словарем и списком?

В Python 2.7 (не в Python 3) я пытаюсь заменить подстроку внутри строки, называемую the_input:

the_input = "~^~~^ASSINF^131d1f15154d4506011601431a4e4419161f10164915434016181f151547101b081972270111043070c19434a0c01160c^5;9;9;10;11~^PIGES^6461166e16483977056703386d324d62151a6c67366441406164166e16396c6a0c68022776621943040965324e7d031670^5@9@9@10@11"

Две подстроки, которые я пытаюсь заменить:

• 131d1f15154d4506011601431a4e4419161f10164915434016181f151547101b081972270111043070c19434a0c01160c и
• 6461166e16483977056703386d324d62151a6c67366441406164166e16396c6a0c68022776621943040965324e7d031670

Я использую значения словаря для замены:

ensemble_cryptage = {
    u'ASSINF': '19150f0d115b49070216164c0804101b151e49454b7806130f12070a405c551006161a03081b0350110d160106561e131c19070a5c1e091e021d07504d41', 
    u'PIGES': '15031505035444020615144d0d0510651102534d5d190d0510651102534d5d0219180b06011a025510061704034b190502151415540212081113174b4157'
}

Чтобы указать правильную строку для замены в the_input, я использую список с подсписками под названием app_chaine_by_three:

app_chaine_by_three = [[u'DB12ABPI', u'ASSINF', u'131d1f15154d4506011601431a4e4419161f10164915434016181f151547101b08197227011e1043070c19434a0c01160c'], [u'DB12ABPI', u'PIGES', u'6461166e16483977056703386d324d62151a6c67366441406164166e16396c6a0c68022776621943040965324e7d031670']]

Это то, что я пробовал:

for cle_ens_crypt,chaine_ens_crypt in ensemble_cryptage.iteritems():
    if cle_ens_crypt in the_input and chaine_ens_crypt not in the_input:
        for liste in app_chaine_by_three:
          the_input = the_input.replace(liste[2], chaine_ens_crypt)

print(the_input)

Однако результаты неверны:

print(the_input)
~^~~^ASSINF^131d1f15154d4506011601431a4e4419161f10164915434016181f151547101b081972270111043070c19434a0c01160c^5;9;9;10;11~^PIGES^19150f0d115b49070216164c0804101b151e49454b7806130f12070a405c551006161a03081b0350110d160106561e131c19070a5c1e091e021d07504d41^5@9@9@10@11

Правильный результат должен быть:

print(the_input)
~^~~^ASSINF^19150f0d115b49070216164c0804101b151e49454b7806130f12070a405c551006161a03081b0350110d160106561e131c19070a5c1e091e021d07504d41^5;9;9;10;11~^PIGES^15031505035444020615144d0d0510651102534d5d190d0510651102534d5d0219180b06011a025510061704034b190502151415540212081113174b4157^5@9@9@10@11