Sachverhalt:
A.
Das Kantonsgericht St. Gallen verurteilte X._, geb. 1. Februar 1957, am 21. April 1998 zweitinstanzlich wegen mehrfacher sexueller Handlungen mit Kindern und mehrfacher Pornographie zu einer Gefängnisstrafe von zweieinhalb Jahren. Gleichzeitig wurde eine ambulante psychotherapeutische Massnahme angeordnet. Am 24. Februar 2000 wurde er bedingt aus dem Strafvollzug entlassen.
Das (damalige) Bezirksgericht Oberrheintal verurteilte X._ am 15. Mai 2001 erneut wegen mehrfacher sexueller Handlungen mit Kindern, mehrfacher sexueller Belästigung sowie mehrfacher Pornographie zu zwei Jahren Gefängnis. Gleichzeitig ordnete es eine ambulante Massnahme an.
Das Justiz- und Polizeidepartement des Kantons St. Gallen (heute Sicherheits- und Justizdepartement [SJD]) widerrief am 2. Oktober 2001 die bedingte Entlassung vom 24. Februar 2000 und ordnete den Vollzug des noch nicht verbüssten Strafrests an. Am 20. August 2002 wies es ein Gesuch von X._ um bedingte Entlassung ab, stellte den Vollzug der ambulanten Massnahme ein und beantragte dem (damaligen) Bezirksgericht Oberrheintal, X._ zu verwahren. Dieses ordnete am 27. Mai 2003 die Verwahrung gestützt auf aArt. 43 Ziff. 1 Abs. 2 StGB an. Die dagegen erhobenen Rechtsmittel wurden abgewiesen (vgl. Urteile des Bundesgerichts 6P.110/2005 und 6S.325/2005 vom 20. Dezember 2005).
Als Folge der Revision des allgemeinen Teils des Strafgesetzbuchs ordnete das Kreisgericht Rheintal am 26. Juni 2007 anstelle der altrechtlichen Verwahrung eine (neurechtliche) stationäre therapeutische Massnahme nach <ref-law> an.
B.
Das SJD lehnte am 13. Februar 2012 das Gesuch von X._ um bedingte Entlassung aus der stationären therapeutischen Massnahme ab, hob die Massnahme auf und beantragte dem Kreisgericht, X._ zu verwahren. Gegen den Aufhebungsentscheid des SJD legte X._ bei der Anklagekammer des Kantons S t. Gallen Beschwerde ein. Diese sistierte das Beschwerdeverfahren am 18. April 2012 bis zum Vorliegen eines rechtskräftigen Entscheids über die beim Kreisgericht beantragte Verwahrung.
Mit Entscheid vom 30. Mai 2012 hob das Kreisgericht die stationäre therapeutische Massnahme auf und ordnete die nachträgliche Verwahrung von X._ gestützt auf Art. 62c Abs. 4 i.V.m. <ref-law> an.
Das Kantonsgericht bestätigte am 13. November 2013 die nachträgliche Anordnung der Verwahrung, hob den kreisgerichtlichen Entscheid aber insofern auf, als damit die stationäre therapeutische Massnahme aufgehoben worden war.
Das Bundesgericht hob diesen Entscheid am 11. Februar 2015 auf (Urteil 6B_227/2014) - im Wesentlichen mit der Begründung, dass vor einem Entscheid betreffend die Verwahrung über die Frage der Aufhebung bzw. der Aussichtslosigkeit der betreffenden stationären Massnahme rechtskräftig entschieden werden müsse.
C.
Das Kantonsgericht wies die Sache in der Folge zu neuerlicher Entscheidung an das Kreisgericht zurück. Die Anklagekammer entschied über die bei ihr hängige (sistierte) Beschwerde betreffend Aufhebung der stationären therapeutischen Massnahme und wies diese ab. Das Kreisgericht ordnete am 2. Dezember 2015 die Verwahrung von X._ an. Gleichzeitig versetzte es ihn in Sicherheitshaft. X._erhob dagegen erneut Beschwerde, welche von der Anklagekammer am 31. März 2016 abgewiesen wurde.
D.
X._ erhebt Beschwerde in Strafsachen vor Bundesgericht und beantragt, den Entscheid der Anklagekammer vom 31. März 2016 aufzuheben; er sei zudem umgehend aus der Sicherheitshaft zu entlassen. Eventuell sei anstelle der Verwahrung erneut eine stationäre Massnahme anzuordnen. Ferner ersucht er für das bundesgerichtliche Verfahren um unentgeltliche Prozessführung und um Verbeiständung.
E.
Die Staatsanwaltschaft beantragt, die Beschwerde abzuweisen und verweist auf das angefochtene Urteil. Die Anklagekammer verzichtet unter Verweis auf das vorinstanzliche Urteil auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer macht geltend, die Vorinstanz hätte die Delikte, welche der Verurteilung aus dem Jahr 1998 zugrunde lagen, nicht als Anlasstaten im Sinne von <ref-law> berücksichtigen dürfen. Im damaligen Strafverfahren seien weder eine stationäre Massnahme noch eine altrechtliche Verwahrung zur Diskussion gestanden. Es fehle deshalb an einem Anknüpfungspunkt gemäss <ref-law>, wonach es einer vorbestehenden erfolglosen stationären Massnahme bedürfe, um die nachträgliche Verwahrung anzuordnen. Die mit Urteil vom 21. April 1998 ausgesprochene ambulante Massnahme sei weder aufgehoben worden noch sei ersichtlich, dass die im Jahr 2001 ausgesprochene ambulante Massnahme diejenige von 1998 umfasse. Ein solches Konstrukt wäre ohnehin gesetzlich nicht vorgesehen. Indem die Vorinstanz beim Entscheid über die nachträgliche Verwahrung auf das Urteil aus dem Jahr 1998 abstelle, verletze sie den Grundsatz ne bis in idem (<ref-law>; Art. 4 Zusatzprotokoll Nr. 7 EMRK).
Ferner rügt der Beschwerdeführer eine Verletzung von <ref-law> i.V.m. <ref-law>. Seine Verfehlungen seien höchstens als mittelschwer einzustufen und erfüllten daher die in <ref-law> an die Anlasstat gestellten Anforderungen nicht. Eine schwere Schädigung der Opfer im Sinne von <ref-law> liege nicht vor. In vergleichbaren Fällen sei noch nie eine Verwahrung ausgesprochen worden. Er sei lediglich zu zweieinhalb respektive zwei Jahren Freiheitsstrafe verurteilt worden. Im Rahmen der Strafzumessung seien im Urteil aus dem Jahr 2001 bei der Täterkomponente auch die einschlägigen Vorstrafen und die erneute Delinquenz während der laufenden Probezeit berücksichtigt worden. Ohne diese belastenden Momente wäre die Strafe wohl noch deutlich tiefer ausgefallen. Die Vorinstanz lasse ausser Acht, dass gemäss Lehre und Rechtsprechung eine Verwahrung erst bei einer Freiheitsstrafe von drei Jahren in Betracht gezogen werden soll.
1.2. Gemäss <ref-law> kann das Gericht auf Antrag der Vollzugsbehörde die Verwahrung anordnen, falls bei Aufhebung einer stationären Massnahme, die aufgrund einer Straftat nach <ref-law> angeordnet wurde, ernsthaft zu erwarten ist, dass der Täter weitere Taten dieser Art begeht. Das Gericht ordnet die Verwahrung an, wenn der Täter eine in <ref-law> ausdrücklich genannte Katalogtat (Mord, vorsätzliche Tötung, schwere Körperverletzung, Vergewaltigung, Raub, Geiselnahme, Brandstiftung, Gefährdung des Lebens) oder eine im Sinne der Generalklausel mit Freiheitsstrafe von fünf oder mehr Jahren bedrohte Tat begangen hat, durch die er die physische, psychische oder sexuelle Integrität einer andern Person schwer beeinträchtigt hat oder beeinträchtigen wollte, und wenn aufgrund einer anhaltenden oder langdauernden psychischen Störung von erheblicher Schwere, mit der die Tat in Zusammenhang stand, ernsthaft zu erwarten ist, dass der Täter weitere Taten dieser Art begeht und die Anordnung einer stationären therapeutischen Massnahme nach <ref-law> keinen Erfolg verspricht (<ref-law>). Die von der Auffangklausel erfassten Delikte dürfen insgesamt nicht weniger schwer wiegen, als dies für die Katalogtaten gilt. Sodann müssen relevante Straftaten und schwere Schädigung kumulativ vorliegen. Die Verwahrung ist als "ultima ratio" nur unter qualifizierten Voraussetzungen möglich. Bei der Beurteilung der Schwere des verursachten Eingriffs ist ein objektiver Massstab anzulegen (<ref-ruling> E. 1.3.3 mit Hinweisen; MARIANNE HEER, Basler Kommentar, Strafrecht I, 3. Aufl., Basel 2013, N. 22 ff. zu <ref-law>; QUELOZ/BROSSARD, Commentaire romand, Code pénal I, 2009, N. 18 zu 64 StGB).
1.3. Der Beschwerdeführer wurde im Jahr 2001 wegen sexueller Handlungen mit Kindern, sexueller Belästigung und Pornografie verurteilt, da er in seiner Wohnung den Penis eines 14-jährigen Knaben über der Hose berührt hatte, als er sich mit diesem zusammen einen Actionfilm ansah. Einige Zeit später, als er dem Knaben einen pornografischen Film vorführte, griff er ihm unter der Hose ans Glied und massierte dieses während einer kurzen Zeit leicht. Anschliessend nahm er die Hand des Knaben, legte sie über der Hose auf sein eigenes Geschlechtsteil und forderte ihn auf, zuzudrücken. Ein anderes Mal zeigte der Beschwerdeführer diesem und einem weiteren, gleichaltrigen Knaben einen Vibrator und führte vor, wie dieser funktioniert, wobei er zuerst dem einen Knaben mit dem Gerät über dessen Oberschenkel und sich anschliessend über der Hose über seinen eigenen Penis fuhr. Der Beschwerdeführer fragte einen der Knaben, ob er ihm den Vibrator einmal in den Anus stecken dürfe. Bei anderer Gelegenheit leckte er einem der beiden Jungen das Ohr ab.
1.3.1. Nach den vorinstanzlichen Erwägungen erfüllen bereits die der Verurteilung aus dem Jahr 2001 zugrunde liegenden Delikte die Anforderungen an die Anlasstat nach <ref-law>. Die Vorinstanz erwägt, eine psychische Beeinträchtigung der Opfer könne erfolgen, ohne dass letztere notwendigerweise von einem äusserlich gravierend in Erscheinung tretenden Übergriff betroffen sein müssten. Im vorliegenden Fall seien die beiden Knaben altersbedingt am Anfang ihrer sexuellen Entwicklung gestanden. Ungewohnte sexuelle Erfahrungen seien durchaus geeignet, nachhaltigen Einfluss auszuüben und diese zu beeinträchtigen. Die Tatsache, dass sich die beiden Opfer trotz Pubertätsalter Erwachsenen anvertraut und die, gerade in dieser Lebensphase besonders schambehafteten, Vorfälle bei der Polizei zur Anzeige gebracht hätten, spreche ebenfalls für einen beträchtlichen Leidensdruck. Schliesslich hätten sie Unterstützung durch die Opferhilfestelle gewünscht. Für eine schwere Beeinträchtigung der sexuellen Integrität spreche auch die Vorgehensweise des Beschwerdeführers. Er habe gezielt ein Vertrauensverhältnis aufgebaut und dieses in der Folge ausgenutzt. Dieses planvolle Vorgehen habe es den Opfern in der konkreten Situation schwer gemacht, sich zu widersetzen, zumal sie dem Beschwerdeführer als erwachsene Person generell unterlegen gewesen seien. Die vorgefallenen Handlungen seien ohne Weiteres geeignet, die ungestörte sexuelle Entwicklung der altersbedingt noch unreifen Knaben zu gefährden bzw. zu beeinträchtigen. Die begangenen Taten würden schwer wiegen und seien mit den Katalogtaten von <ref-law> vergleichbar.
1.3.2. Sexuelle Verfehlungen gegenüber Kindern gehören prinzipiell zu den gravierenden Straftaten. Den Tatbestand von <ref-law> erfüllen Handlungen, die nach Art und Intensität sehr verschieden sind. Dass nicht jede dieser Handlungen im Sinne des weit gefassten Tatbestands geeignet ist, namentlich die sexuelle und psychische Integrität des Opfers schwer zu beeinträchtigen, ist offensichtlich. Die vom Beschwerdeführer begangenen Übergriffe erreichen, ohne diese verharmlosen zu wollen, innerhalb der Bandbreite möglicher sexueller Handlungen mit Kindern das hinsichtlich ihrer Schwere und Intensität erforderliche Mindestmass nicht. Damit fehlt es an einer relevanten Straftat und somit an einer zwingenden Voraussetzung von <ref-law>. Der Vorinstanz ist insofern zuzustimmen, als dass ungewollte sexuelle Erfahrungen grundsätzlich geeignet sind, nachhaltigen Einfluss auf die sexuelle Entwicklung der Betroffenen auszuüben und diese zu beeinträchtigen. Im vorliegenden Fall wiegen die Tathandlungen jedoch nicht derart schwer, dass ohne Weiteres von einer gravierenden Beeinträchtigung ausgegangen werden müsste. In diesem Zusammenhang nicht zu berücksichtigen sind die von der Vorinstanz angeführten subjektiven Auswirkungen der Übergriffe auf die Opfer. Entscheidend ist einzig, ob das konkrete Tatverhalten aufgrund seiner Eingriffsintensität nach der allgemeinen Lebenserfahrung geeignet ist, auf Seiten der Opfer eine schwerwiegende Integritätsbeeinträchtigung zu bewirken (Urteil 6B_109/2013 vom 19. Juli 2013 E. 4.3.3).
Insgesamt erreichen die Handlungen die Erheblichkeitsschwelle von <ref-law> nicht. Inwiefern eine schwere Beeinträchtigung der physischen, psychischen oder sexuellen Integrität vorliegen soll, ist ebenfalls nicht ersichtlich. Die Vorinstanz verletzt Bundesrecht, indem sie die Verurteilung aus dem Jahr 2001 als Anlasstaten im Sinne von <ref-law> qualifiziert.
1.4. Weiter stellt die Vorinstanz auf die dem Urteil aus dem Jahr 1998 zugrunde liegenden Delikte ab. Die damalige Verurteilung wegen mehrfacher sexueller Handlungen mit Kindern sowie mehrfacher Pornographie betrafen diverse Opfer und eine grössere Zahl von Tathandlungen. Der Beschwerdeführer baute auf verschiedene Arten ein Vertrauensverhältnis zu den Kindern auf (Jugendfussball, Schiedsrichtertätigkeit, Auftritte als Zauberer, Nachhilfestunden etc.). Ihm wird vorgeworfen, einen Knaben ausgezogen, ihn am ganzen Körper massiert, an Ohren und Genick geleckt und dessen Glied gerubbelt zu haben. Weiter habe er sich sein eigenes Glied reiben lassen und sich vor dem Jungen selbst befriedigt. In einem weiteren Fall drang der Beschwerdeführer anal in einen Knaben ein. Insbesondere dieser letzte Vorfall ist verglichen mit den vorerwähnten Delikten als gravierend einzustufen. Die Verurteilungen aus dem Jahr 1998 fallen daher als Anlasstaten nicht von vornherein ausser Betracht und bedürfen einer umfassenden Beurteilung.
1.4.1. Nach der Vorinstanz entsprechen die Taten in ihrer Schwere ohne Weiteres den Katalogtaten von <ref-law>. Darüber hinaus hätten die Übergriffe nachweislich zu einer schweren Beeinträchtigung der psychischen und sexuellen Integrität der Opfer geführt. Vom Beschwerdeführer gehe eine sehr hohe Gefahr neuerlicher sexueller Übergriffe auf Kinder aus. Dessen persönliche Freiheit sei weniger hoch einzustufen als das Wohl seiner mutmasslich künftigen Opfer. Aufgrund dessen sei die nachträgliche Verwahrung anzuordnen.
1.4.2. Bei jeder strafrechtlichen Sanktion, die in verfassungsmässig garantierte Grundrechte eingreift, bleibt zu fragen, ob sie dem Gebot der Verhältnismässigkeit entspricht (<ref-law>). Dieser Grundsatz gilt im gesamten Massnahmerecht, sowohl bei der Anordnung von Massnahmen als auch bei den Folgeentscheidungen. Er wird im StGB konkretisiert. <ref-law> besagt, dass der mit einer Massnahme verbundene Eingriff in die Persönlichkeitsrechte des Täters im Hinblick auf die Wahrscheinlichkeit und Schwere weiterer Straftaten nicht unverhältnismässig sein darf. Was das konkret bedeutet, hängt entscheidend von der Gewichtung der im Einzelfall einander widerstreitenden Interessen ab, d.h. insbesondere von der Grösse der Gefahr, der die Massnahme begegnen soll, und der Schwere des Eingriffs in die Rechte des Betroffenen, der mit ihr verbunden ist. Eine unverhältnismässige Massnahme darf nicht angeordnet oder weiter vollzogen werden.
Der Verhältnismässigkeitsgrundsatz verlangt, dass die Sicherheitsbelange der Allgemeinheit und der Freiheitsanspruch des Verwahrten als wechselseitiges Korrektiv gesehen und im Einzelfall gegeneinander abgewogen werden. Bei langandauernder Unterbringung gewinnt der Freiheitsanspruch des Eingewiesenen zunehmend an Gewicht. Dem Verhältnismässigkeitsgebot kommt insofern ähnlich dem Schuldprinzip Begrenzungsfunktion zu.
Bei der erforderlichen Abwägung der sich widerstreitenden Interessen hat der Richter die vom Täter ausgehenden Gefahren zur Schwere des mit der Massnahme verbundenen Eingriffs ins Verhältnis zu setzen. Es kommt insbesondere darauf an, ob und welche Straftaten vom Massnahmeunterworfenen drohen, wie ausgeprägt das Mass der Gefährdung ist und welches Gewicht den bedrohten Rechtsgütern zukommt. Je schwerer die Delikte wiegen, die der Massnahmeunterworfene in Freiheit begehen könnte, desto geringer kann die Gefahr sein, die eine freiheitsentziehende Massnahme rechtfertigt, und umgekehrt (<ref-ruling> E. 2a.; siehe auch <ref-ruling> E. 2a).
Das Spannungsverhältnis zwischen dem Freiheitsanspruch des Massnahmeunterworfenen und dem Sicherungsbedürfnis der Allgemeinheit vor zu erwartenden erheblichen Rechtsgutsverletzungen verlangt nach einem vertretbaren Ausgleich. Je länger die Massnahme und damit der Freiheitsentzug für den Betroffenen dauert, desto strenger werden die Anforderungen an die Wahrung der Verhältnismässigkeit. Was im Sinne von <ref-law> relevante schwere Straftaten sind, unterliegt deshalb mit zunehmender Dauer des Freiheitsentzugs einer Bewertungsanpassung. Wohl kann sein, dass die künftig in Freiheit zu erwartenden Straftaten unverändert den Taten entsprechen, auf die die Verurteilung zurückgeht. Mit zunehmender Vollzugsdauer mögen diese Taten in ihrer Schwere aber nicht mehr ausreichen, um eine weitere Aufrechterhaltung der Massnahme respektive deren nachträgliche Anordnung zu rechtfertigen. Der Einfluss des gewichtiger werdenden Freiheitsanspruchs des Massnahmeunterworfenen stösst jedoch dort an die Grenzen, wo es nach Art und Mass der drohenden Gefahren für die Rechtsgüter des Einzelnen und der Allgemeinheit unvertretbar erscheint, den Massnahmeunterworfenen bedingt in die Freiheit zu entlassen bzw. die Massnahme aufzuheben (Urteil 6B_109/2013 vom 19. Juli 2013 E. 4.4 mit Hinweisen).
1.4.3. Mehrheitlich sind die vom Beschwerdeführer begangenen Übergriffe aus dem Jahr 1998 hinsichtlich ihrer Schwere und Ausgestaltung mit jenen aus dem Jahr 2001 vergleichbar. Sie erreichen damit die für die Anordnung der Verwahrung erforderliche Schwere nicht. Demgegenüber sticht der anale Geschlechtsverkehr mit einem Jungen als deutlich schwererer Übergriff hervor. Dabei handelt es sich grundsätzlich um ein gravierendes Delikt, welches aufgrund seiner Eingriffsintensität nach der allgemeinen Lebenserfahrung geeignet ist, auf Seiten der Opfer eine schwerwiegende Integritätsbeeinträchtigung zu bewirken. Hinsichtlich seiner Schwere ist es ohne Weiteres mit der Katalogtat der Vergewaltigung vergleichbar. Hinsichtlich der Legalprognose stützt sich die Vorinstanz auf das Gutachten von Dr. med. A._ vom 10. August 2013. Demgemäss sei die Rückfallgefahr für ein Sexualdelikt der Qualität einer sexuellen Handlung mit Kindern sehr hoch. Eine stabile Verminderung des strukturellen Rückfallrisikos habe durch die bisher durchgeführten therapeutischen Interventionen nicht erzielt werden können. Der Beschwerdeführer beanstandet weder die gutachterliche Einschätzung noch die vorinstanzlichen Erwägungen.
Nebst der Tatschwere und der Rückfallgefahr muss vorliegend besonderes Augenmerk auf den Zeitfaktor gelegt werden. Je länger die Massnahme und damit der Freiheitsentzug für den Betroffenen dauert, desto strenger werden die Anforderungen an die Wahrung der Verhältnismässigkeit (E. 1.4.2). Es ist daher zu prüfen, ob die Anordnung der Verwahrung einer Verhältnismässigkeitsprüfung nach wie vor standhält. Der Beschwerdeführer befindet sich seit dem Jahr 2000 im Strafvollzug respektive der Verwahrung oder einer stationären therapeutischen Massnahme. Dieser Zeitraum ist unter anderem auch gemessen an den ausgefällten Strafen von zweieinhalb und zwei Jahren relativ lang. Der Eingriff in die Freiheitsrechte des Beschwerdeführers wiegt damit schwer und die Anordnung der Verwahrung würde einen weiteren gravierenden Eingriff darstellen. Die beabsichtigte Massnahme und die damit verbundene Grundrechtsbeschränkung ist mit den Anlasstaten und der Schwere der in Freiheit zu erwartenden Taten abzuwägen.
Die zu erwartenden Delikte, die sexuellen Handlungen mit Kindern, gehen mit der Verletzung eines hochwertigen Rechtsguts, nämlich der ungestörten sexuellen Entwicklung von Kindern einher. Dass es auch zu höhergradigen körperlichen Integritätsverletzungen der Opfer kommen könnte, ist jedoch nicht ersichtlich. Die Vorgehensweise des Beschwerdeführers war jeweils nicht von körperlicher Gewalt geprägt. Vielmehr nutzte er die Situation des zuvor aufgebauten Vertrauensverhältnisses aus. Besonders ins Gewicht fällt vorliegend der Analverkehr mit einem Jungen als schwerster Verstoss, der indessen einmalig blieb. Unter Berücksichtigung der gesamten Umstände erweisen sich die verübten und die zu erwartenden Delikte als mässig schwer. Der massive Eingriff in die Freiheitsrechte des Beschwerdeführers wird daher nicht durch den Sicherheitsanspruch der Allgemeinheit aufgewogen. Die Anordnung der Verwahrung erweist sich vorliegend als unverhältnismässig. Nicht gefolgt werden kann der vorinstanzlichen Argumentation, wonach das Bundesgericht hinsichtlich des Beschwerdeführers die Verwahrung bereits einmal bestätigt habe. Das bundesgerichtliche Urteil vom 20. Dezember 2005 bezog sich auf die altrechtliche Verwahrung nach aArt. 43 StGB, deren Voraussetzungen mit denjenigen von <ref-law> nicht vollständig vergleichbar sind. Daraus kann deshalb weder zu Gunsten noch zu Lasten des Beschwerdeführers etwas abgeleitet werden. Da weder die Delikte aus dem Jahr 2001 noch jene aus dem Jahr 1998 die Anforderungen von <ref-law> erfüllen, erübrigt sich eine Auseinandersetzung mit der Frage, ob der vorinstanzliche Entscheid gegen das Verbot der doppelten Strafverfolgung verstösst. Das angefochtene Urteil ist aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
2.
Der Beschwerdeführer beantragt im Weiteren, er sei umgehend aus der Sicherheitshaft zu entlassen. Dem Antrag kann nicht stattgegeben werden. Zwar sind die Voraussetzungen für die nachträgliche Anordnung der Verwahrung nicht gegeben. Dies hat jedoch nicht automatisch die Entlassung des Beschwerdeführers in die Freiheit zur Folge. Vielmehr haben die kantonalen Behörden nach dem Scheitern einer Massnahme über das weitere Vorgehen zu befinden. So kann sie beispielsweise, wie vom Beschwerdeführer selber im Eventualstandpunkt beantragt, eine andere Massnahme anordnen (vgl. <ref-law>).
3.
Die Beschwerde ist gutzuheissen. Der angefochtene Entscheid ist aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen.
Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (<ref-law>). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gegenstandslos. Der Kanton St. Gallen hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid der Anklagekammer des Kantonsgerichts St. Gallen vom 31. März 2016 wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton St. Gallen hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und der Anklagekammer des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 8. Dezember 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Schär