Mycket har förändrats sedan All Saints första laddning på scenen 1997. På den tiden hade Tony Blair just vunnit valet, Oasis var på nummer ett med Be Here Now, och världens största hemsida var en sida full av dansande hamstrar.
Popmusik var i doldrums - detta var året för Barbie Girl och Gary Barlows soloalbum - så Shaznay Lewis, Melanie Blatt och systrarna Natalie och Nicole Appleton var en välkommen frisk fläkt.
Positionerade som ett trovärdigt alternativ till Spice Girls, skrev de sitt eget material, klädda i gatusmarta kläder och undvek chirpy koreografi av andra tjejgrupper (deras signatur drag var en apatisk axelryckning).
Men det var svårt att vara kvinna i den mansdominerade musikindustrin.
Kvinnliga popstjärnor förväntades klä sig provokativt - en avslöjande fotoshooting för FHM var en rit av passage - och Alla helgon, aldrig medvetet i besittning av ett leende, avfärdades ofta som "svår" eller "sulky".
Det var orättvist och sexistiskt, protesterar Melanie.
– Många Britpop-grupper då skulle agera mycket arrogant och väldigt stroppigt, men det sågs aldrig som något negativt, säger hon.
"Vi var inte hälften så dåliga - men om vi inte ville le en dag, eller vi var inte riktigt intresserade av att göra en intervju, skulle vi märkas som stroppiga kor."
Sexismen spillde över i deras TV-framträdanden, och bandet ryser när de minns en traumatisk Top of the Pops inspelning.
"De filmade bilder av oss att använda som bakgrund", säger Shaznay, "och de ville att vi skulle ta av oss topparna."
Producenterna, förklarar de, ville skjuta bandet från axlarna upp, vilket gav intryck av att de uppträdde naken.
" Visionen var att vi såg nakna ut och inte ville ha den visionen", tillägger Natalie. "Men eftersom det var en så stor show, fick vi höra "om du inte gör det, får du inte gå med i showen", säger Melanie.
"Tjejen som arbetade med oss var i tårar för att hon försökte kämpa mot vårt hörn", fortsätter Natalie. – Det slutade med att vi fick kompromissa med producenterna. Vi tappade våra toppar till här [indikerar hennes armhålor] så det skulle se ut som vi var topless."
"Vi gjorde det, men vi var kaxiga över det", säger Nicole. "Återigen blev vi märkta som svåra."
En talesman för BBC sade: "Vi kan inte kommentera något som påstås ha hänt för nästan 20 år sedan, men idag försöker vi se till att alla som arbetar på BBC gör det i en miljö där de är bekväma."
Nitton år senare, klämmade ihop sig på en soffa i västra London, är bandet allt annat än stroppigt. De snubblar över varandras ord, byter skämt och låser sina bandkamrater ut från hotellrum som ett sätt att överleva en lång dag av pressintervjuer. Till och med toppen av Pops-incidenten är utskrattad.
"Nu för tiden skulle det vara som, 'Vill du se mig naken? Okej! Visst!" Skämtar Natalie. "Jag tar av mig byxorna den här gången!"
Deras kamratskap är något av en överraskning. Efter två multi-platinum album imploderade bandet 2001 över det omtvistade ägandet av en stridsjacka.
"Att vara i en grupp är som att vara i ett äktenskap, och just nu går vi igenom en riktigt tuff tid," Nicole sade strax före splittringen. Ett senare uttalande bekräftade att bandet var "på is" för att "rensa luften mellan sig".
De tidigare skolkamraterna talade inte på åratal, men broar byggdes under en kort återförening 2006 och stärktes på en nostalgiturné med Backstreet Boys för tre år sedan.
"Men vi blir ändå tillfrågade om jackan varje dag", skrattar Nicole.
Efter 2013 års turné ville bandet gärna fortsätta, men deras ledning föreslog att de behövde nytt material innan de åkte tillbaka på vägen.
"Shaz nominerades till att skriva albumet", säger Natalie, "men det fanns ingen mästerlig plan, ingen som berättade för oss, "detta är den vision vi har för dig". Det fanns ingen press. Och hon drog ut en fantastisk skiva."
Efter ett år i studion tillkännagavs All Saints comeback på nyårsdagen via Twitter men svaret var mer nyfikenhet än entusiasm tills bandet presenterade sin nya singel på Chris Evans Radio 2 Breakfast show.
En strejk påminner om det drömska, lycksaliga ljudet av deras första träff på Pure Shores, med kvartettens silkesharmonier som provocerar fram 90-tals nostalgi.
– Det var en naturlig första singel, säger Shaznay. "Vi behövde egentligen inte ens diskutera det så mycket. Det var den första låten vi spelade in tillsammans igen. Det är bara en bra början."
Även om texten skrevs av Shaznay, utlöstes den av Nicoles skilsmässa från Liam Gallagher. Paret delade sig 2013 efter Oasis stjärna ringde sin fru på semester och erkände att far ett barn med en annan kvinna. One Strike hänvisar till det telefonsamtalet, och "hur ditt liv kan förändras på ett ögonblick".
"Som alla har sett och hört [i pressen], var jag borta när saker gick ner", säger Nicole. "Jag var tvungen att ta mig samman för att jag hade min familj och mina barn runt mig men, efter ett par dagar av att låta det sjunka in, var jag i telefon med Shaz för en lång tid, bara förklara [hur] jag kom igenom det. Du vet, att behöva stå upp mot det, istället för att bli ett slags offer.
"Nästa sak jag visste € € hon spelade [en Strike] för mig och jag sjöng med. Då sade hon: "Lyssnade du på vad sången handlar om?" Och plötsligt föll pennyn och jag tänkte: "Herregud. Det är vårt telefonsamtal! "
– Saken är den att för mig har jag hanterat allt med värdighet och stöd från flickorna och min familj. Jag tycker att låten representerar det mycket väl. Jag känner mig inte ledsen när jag hör det, jag känner mig helt befriad. Det är en mycket positiv låt. Det är toppen. Det fångade verkligen ögonblicket."
Som Nicole berättar den här historien, tittar Shaznay tyst på henne med en skyddande blick från en mor. Vid 40 års ålder är hon bandets yngsta medlem - men de andra ser upp till henne som ledare; den de vänder sig till för att få råd och, säger Nicole, "en bra lyssnare".
"Hon skriver poesi", säger Natalie. "Ibland, när jag börjar tänka på det hon skrivit, så blåser det mig i huvudet."
I 10-års gapet mellan albumen har Shaznay fortsatt att arbeta som låtskrivare och samarbeta med liken Little Mix och Sugababes - så hur flyttade hon varumärket All Saints sound?
"Jag kan faktiskt inte förklara det", säger hon. "Jag tror att en av de grundläggande ingredienserna för ljudet är våra röster tillsammans och den typen av slits tillbaka på plats."
Men, säger hon, allas röst förändrades under de mellanliggande åren, vilket innebär att arrangemangen måste skrivas om för deras kommande turné.
"Jag brukade göra den höga harmonin, nu gör jag den låga," förklarar Melanie. "Mina kulor har tappats."
Inte för första gången, bandet cackle med skratt, lyckligt oberörd av media träning som dikterar de flesta moderna intervjuer.
"Konstnärer tenderar att vara mer försiktiga med vad de säger nu, eftersom det kan röra sig in i stratosfären så snabbt", säger Shaznay. "Men även om det är förståeligt, tycker jag att det är synd - eftersom man förlorar essensen av vem en konstnär är. Man får inte en riktig känsla för någon, så alla blir generiska."
Kanske är det kärnan i All Saints vädjan - de är inte karikatyrer, men verkliga kvinnor som omfamnar sina styrkor och brister.
Är denna återförening början på ett nytt kapitel?
"När vi hade avslutat denna platta kunde vi lätt ha fortsatt eftersom vi när vi kom till slutet hade börjat utforska olika ljud", säger Shaznay. "Jag tror att om vi hör mer material som vi inspireras av, kommer vi definitivt att skriva mer."
"Men vi har ingen brådska", varnar Melanie. "Vi tar vår tid."
De kommer väl inte att vänta i tio år till?
"Det tar mig så lång tid", säger Nicole, "att kliva av soffan."
Alla Saints album Red Flag är nu ute på London Records.
Reformerad popgrupp All Saints diskuterar sitt nya album och minns den sexism de mötte i sin första svallning av berömmelse.