Citation: 4A_460/2020 E. A

A.a. A.________ et B.________ (ci-après: les locataires, les demandeurs ou les recourants) ont pris à bail auprès de C.________ SA (ci-après: la bailleresse, la défenderesse ou l'intimée) un local d'une surface de 24 m 2 (ci-après: le local) au premier étage du centre commercial C.________ (ci-après: le centre). Le local est destiné à l'exploitation d'un commerce d'articles cadeaux et de produits artisanaux. Le bail a été conclu pour une période initiale s'étendant du 1er septembre 1998 au 30 septembre 2003, prolongeable ensuite d'année en année, et pour un loyer proportionnel au chiffre d'affaires dont le montant minimal annuel est de 13'200 fr., charges non comprises. Les parties sont convenues d'un deuxième contrat de bail puis d'un avenant. Le 14 septembre 2012, les parties ont conclu un troisième contrat de bail pour une durée de cinq ans, soit du 1er octobre 2013 au 30 septembre 2018, renouvelable tacitement de cinq ans en cinq ans sauf résiliation moyennant un préavis d'une année. Le loyer proportionnel a été fixé à 10 % du chiffre d'affaires hors TVA, le loyer minimal annuel étant de 20'400 fr. Celui-ci est par ailleurs indexé à l'indice suisse des prix à la consommation dès la deuxième année. A.b. Par avis du 25 septembre 2017 notifié à A.________, la bailleresse a résilié le bail pour le 30 septembre 2018 (ci-après: le premier congé). Le 6 octobre 2017, elle a motivé le congé par le fait qu'elle souhaitait procéder à des changements dans l'assortiment du centre, les prestations des locataires ne correspondant plus à ses attentes, à ses standards et/ou à ses besoins. Après que les locataires ont contesté le congé et invoqué sa nullité, la bailleresse l'a retiré en raison du fait qu'il avait été notifié uniquement à A.________. A.c. Par avis du 20 mars 2018 notifié aux locataires, la bailleresse a résilié le bail pour le 30 septembre 2023, se prévalant du motif invoqué le 6 octobre 2017 (ci-après: le second congé).